题解：AT_abc327_d [ABC327D] Good Tuple Problem

· · 题解

这题显然是种类并查集做法最简单啊，题解区里怎么没有这种做法？这篇题解就来讲种类并查集做法。

双倍经验：P1892 [BOI2003] 团伙。

Solution

由于 X_i 有 0 或 1 两种取值，考虑种类并查集，把它拆成 a_i 和 a_i'，a_i 表示 X_i=0 时的情况，a_i' 表示 X_i=1 时的情况。

对于每个限制 X_{S_i}\not=X_{T_i}，如果 a_{S_i} 和 a_{T_i} 在同一连通块内，就说明 X_{S_i}=X_{T_i}，显然是不合法的，就输出 No，否则就有两种情况：如果 X_{S_i}=1，那么 X_{T_i}=0，这种情况就把 a_{S_i}' 和 a_{T_i} 连一条边，如果 X_{S_i}=0，那么 X_{T_i}=1，这种情况就把 a_{S_i} 和 a_{T_i}' 连一条边。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m,a[N],b[N];
int fa[N<<1|1];

int find(int x) {
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d",a+i);
    for (int i=0;i<m;i++) scanf("%d",b+i);
    for (int i=1;i<=n<<1;i++) fa[i]=i;
    for (int i=0;i<m;i++) {
        int x=find(a[i]),y=find(b[i]);
        if (x==y) return printf("No"),0;
        fa[find(n+a[i])]=y,fa[find(n+b[i])]=x;
    }
    printf("Yes");
    return 0;
}