洛谷-食物链(扩展域并查集)

原题地址

食物链

动物王国中有三类动物 $A,B,C，$A,B,C，这三类动物的食物链构成了有趣的环形。 $A$A 吃 $B，B$B，B

吃 $C，C$C，C 吃 $A$A。

现有 $N$N 个动物，以 $1－N$1－N 编号。每个动物都是 $A,B,C$A,B,C 中的一种，但是我们并不知道

它到底是哪一种。

有人用两种说法对这 $N$N 个动物所构成的食物链关系进行描述：

第一种说法是“ $1XY$1XY”，表示 $X$X 和 $Y$Y 是同类。

第二种说法是“ $2XY$2XY”，表示 $X$X 吃 $Y$Y 。

此人对 $N$N 个动物，用上述两种说法，一句接一句地说出 $K$K 句话，这 $K$K 句话有的是真

的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话

• 当前的话中 $X$X 或 $Y$Y 比 $N$N 大，就是假话

• 当前的话表示 $X$X 吃 $X$X，就是假话

你的任务是根据给定的 $N$N 和 $K$K 句话，输出假话的总数。

思路

将 $A,B,C$A,B,C 之间的关系用三个维度来记录, 三个维度的所有变量一开始都有自己的标号，最后据题意进行合并

//#pragma comment(linker, "/STACK:102400000,102400000") 
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}

const int maxn = 5e4+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int N, K;

int a[3*maxn];

int find(int p) { return p==a[p]?p:a[p]=find(a[p]); }

void link(int pi, int pj) {
    int x=find(pi);
    int y=find(pj);
    if(x!=y) a[x]=y;
}

int main() {
    //ios::sync_with_stdio(false);
    N=read(), K=read();
    for(int i=1; i<=3*N; ++i) a[i]=i; //扩展域标号, 1~N表示自身，N+1~2N表示吃谁，2N+1~3N表示被谁吃
    int cnt=0;
    while(K--) {
        int q=read(), x=read(), y=read();
        if(x>N||y>N) cnt++;
        else {
            if(q==1) {
                if(x==y) continue;
                if(find(x)==find(y+N)||find(x+N)==find(y)) cnt++; //如果x吃y，或者y吃x，则不满足
                else link(x,y), link(x+N,y+N), link(x+2*N,y+2*N);
            }
            else {
                if(x==y) {
                    cnt++;
                    continue;
                }
                if(find(x)==find(y)||find(x+2*N)==find(y)) cnt++; //如果x与y同类或者x被y吃，则不满足
                else link(x,y+2*N) ,link(x+N,y), link(x+2*N,y+N);
            }
        }
    }
    printf("%d\n", cnt);
}