题解
给定一系列关系,然后求出最多有几个坏人
关系如下:
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