CF1594D The Number of Imposters 题解

leexzq · 2021-10-11 11:41:47 · 题解

题意

在游戏 Among them 中，有 n 个人，其中每个人可能是好人或杀手。

好人永远说真话，杀手永远说假话。

给出 m 条对话，即 i 说 j 是好人/杀手。

根据这些对话，判断这 n 个人中最多有多少杀手，若对话自相矛盾则输出 -1。

solution

我们想想每条对话代表什么：

• 如果一个人说另一个人是杀手，则他们属于不同阵营（互踩）。

• 如果一个人说另一个人是好人，则他们属于相同阵营（发金水）。

而很明显这些关系是可以传递的，而每个人之间的关系又有多种，所以我们可以想到扩展域并查集。

用两个点表示第 i 个人，其中第 i 号点表示与他身份相同的人的集合（正集），第 i+n 号点表示与他身份不同的人的集合（反集）。

对每一条对话，若说别人为好人，合并他们的正反集与对方的合并，否则把他们的正集与对方的反集合并，最后判断对立的两个集合大小，取较大值求和即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
const int N=2e5+10,M=5e5+10;
int fa[N*2],siz[N*2],n,m,a[M],x[M],y[M],b[M];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void merge(int x,int y)
{
    if(x==y)return;
    fa[x]=y,siz[y]+=siz[x];
}
//扩展域并查集 
int solve(int ans=0)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1,b[i]=0;
    for(int i=n+1;i<=2*n;i++)fa[i]=i,siz[i]=0,b[i]=0;
    for(int i=1;i<=m;i++)
    {
        string s;
        cin>>x[i]>>y[i]>>s;
        if(s[0]=='i')a[i]=1;
        else a[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x1=get(x[i]),y1=get(y[i]),x2=get(x[i]+n),y2=get(y[i]+n);
        if(a[i]==1)
        {
            if(x1==y1||x2==y2)return -1;
            merge(y2,x1),merge(x2,y1);
        }
        else
        {
            if(x1==y2||x2==y1)return -1;
            merge(x1,y1),merge(x2,y2);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int x1=get(i),x2=get(i+n);
        if(!b[x1]&&!b[x2])ans+=max(siz[x1],siz[x2]),b[x1]=b[x2]=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)cout<<solve()<<endl;
}