首页 > 其他分享 >D. The Number of Imposters

D. The Number of Imposters

时间:2024-06-13 23:45:49浏览次数:21  
标签:fx sizes int Number fa 坏人 Imposters now

原题链接

题解

给定一系列关系,然后求出最多有几个坏人

关系如下:
1.如果 \(A\) 说 \(B\) 是好人

  • 若 A 是好人 ,则 B 也是好人
  • 若 A 是坏人 ,则 B 也是坏人

2.如果 A 说 B 是坏人

  • 若 A 是好人 ,则 B 是坏人
  • 若 A 是坏人 ,则 B 是好人

我们构建集合,令其含义为:只要有一个人身份确认,那么集合内所有人的身份也就确认了
i 代表 i 是好人
i+n 代表 i 是坏人

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[400005];
int sizes[400005]={0};//代表以它为首的集合包含的坏人的大小,如果为0代表它不为集合首,或者已经被记录过
int finds(int now)
{
    if(now==fa[now]) return now;

    sizes[fa[now]]+=sizes[now];
    sizes[now]=0;
    return fa[now]=finds(fa[now]);
}

void connect(int x,int y)
{
    int fx=finds(x),fy=finds(y);
    if(fx==fy) return ;//这里的细节注意
    fa[fx]=fy;
    sizes[fy]+=sizes[fx];
    sizes[fx]=0;
}

int solve()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(finds(i)==finds(i+n))  return -1;
        ans+=max(sizes[finds(i)],sizes[finds(i+n)]);
        sizes[finds(i)]=sizes[finds(i+n)]=0;//被记录过的集合赋值为零
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            fa[i+n]=i+n;
            sizes[i+n]=1;
            sizes[i]=0;
        }

        for(int i=1;i<=m;i++)
        {
            int x,y;
            string op;
            cin>>x>>y>>op;
            if(op[0]=='c')
            {
                connect(x,y);
                connect(x+n,y+n);
            }
            else
            {
                connect(x+n,y);
                connect(x,y+n);
            }
        }

        cout<<solve()<<endl;
    }
    return 0;
}

标签:fx,sizes,int,Number,fa,坏人,Imposters,now
From: https://www.cnblogs.com/pure4knowledge/p/18246965

相关文章

  • manim边学边做--DecimalNumber
    DecimalNumber是Mobjects分类中专门用来显示数字的一个class。它的主要功能是提供一种展示数字的方式,包括整数和浮点数。DecimalNumber在manim各个模块中的位置如上图中所示。1.主要参数虽然只是数字的展示,但是manim也提供了丰富的参数,可以在不同的场景中用不同的展示方式。其......
  • 运维系列:nginx 重启报nginx: [error] invalid PID number ““ in “/run/nginx.pid“
    这nginx重启报nginx:[error]invalidPIDnumber““in“/run/nginx.pid“nginx重启报nginx:[error]invalidPIDnumber““in“/run/nginx.pid“为何出现这种原因?解决方式:nginx重启报nginx:[error]invalidPIDnumber““in“/run/nginx.pid“......
  • JavaScript Number 对象
     JavaScript只有一种数字类型。可以使用也可以不使用小数点来书写数字。JavaScript数字JavaScript数字可以使用也可以不使用小数点来书写:实例varpi=3.14;//使用小数点varx=34;//不使用小数点极大或极小的数字可通过科学(指数)计数法来写:实例vary=1......
  • QOJ #1285.Stirling Number
    一道非常厉害的题目。题意求:\[\sum_{i=0}^{m}c(n,i)\modp\]其中\(c(n,i)\)为无标号第一类斯特林数,且有\(n,m\le10^{18},p\le10^6\)。Sol考虑一个性质:\[x^{\overlinep}\equivx^p-x\modp\]证明比较简单,考虑费马小定理,\(x^p\equivx\modp\)。而\(x,x+1,\cdots,x+......
  • How to use JavaScript BigInt and Number.prototype.toString to handle the super l
    HowtouseJavaScriptBigIntandNumber.prototype.toStringtohandlethesuperlargeintegerproblemsAllInOne如何使用JavaScriptBigInt和Number.prototype.toStringg处理超大整数问题errorsfunctionplusOne(digits:number[]):number[]{letn=parseI......
  • Leetcode 313. Super Ugly Number
    ProblemAsuperuglynumberisapositiveintegerwhoseprimefactorsareinthearrayprimes.Givenanintegernandanarrayofintegersprimes,returnthenthsuperuglynumber.Thenthsuperuglynumberisguaranteedtofitina32-bitsignedintege......
  • LeetCode 1411. Number of Ways to Paint N × 3 Grid
    原题链接在这里:https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/description/题目:Youhavea grid ofsize nx3 andyouwanttopainteachcellofthegridwithexactlyoneofthethreecolors: Red, Yellow, or Green whilemakingsuretha......
  • [LeetCode] 1365. How Many Numbers Are Smaller Than the Current Number 有多少小于
    Giventhearray nums,foreach nums[i] findouthowmanynumbersinthearrayaresmallerthanit.Thatis,foreach nums[i] youhavetocountthenumberofvalid j's suchthat j!=i and nums[j]<nums[i].Returntheanswerinanarray.Example1......
  • spark sql中的FORMAT_NUMBER和ROUND函数
    一、例子:FORMAT_NUMBER(ROUND(value,2),'0.00')二、ROUND函数的作用:用于将数值字段舍入到指定的小数位数,如果未指定小数位数,则默认将数字舍入到最接近的整数。三、FORMAT_NUMBER函数的作用:用于将数字格式化为指定的格式,而不是进行舍入。四、两者的区别:如果小数点后面的数字,最......
  • 【YashanDB知识库】kettle从DM8的number类型同步到YashanDB的varchar类型,存入是科学计
    【标题】kettle从DM8的number类型同步到YashanDB的varchar类型,存入是科学计数法形式的数据【问题分类】数据导入导出【关键字】数据同步,number类型,科学计数法【问题描述】客户查询不到准确数据,只看到科学计数法展示的字符串。number类型存入到Oracle(MySQL)的varchar类型是正常......