NC18884 食物链（并查集+拆点+数理逻辑）

题目传送门

题目描述

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

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

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

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

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

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1）当前的话与前面的某些真的话冲突，就是假话；

2）当前的话中X或Y比N大，就是假话；

3）当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1≤N≤50,000）和K句话（0≤K≤100,000），输出假话的总数。

输入描述:

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

输出描述:

只有一个整数，表示假话的数目。

示例1

输入

输出

说明

Solution：

First，根据动物之间是否同类，吃和被吃的关系，可以联想到并查集（PS：只要 $x$ 和 $y$ 之间有关系就将其并在一个集合中）

Second，题目中要我们输出假话的数量，我们可以把在前面输入的数据都默认为真，后面输入的数据一旦和前面的有矛盾，就可以判断其是假话

Third，题目没有告诉我们每个动物究竟是属于A,B,C哪一类，那么我们不妨采用拆点的思想，开一个3倍长度的数组， $[a, a + n]$ 存放这个每个动物 $i$ 是A类时，它的父亲节点是哪一个， $[a + n + 1, a + 2 * n]$ 同理。

具体怎么判断呢？如果输入的数据是 $1 x y$ ，说明 $x$ 和 $y$ 是同类，如果 $x$ 和 $y + n$ ， $x$ 和 $y + 2 * n$ 在同一集合中， $x + n$ 和 $y + 2 * n$ ， $x + n$ 和 $y$ 在同一个集合中， $x + 2 * n$ 和 $y$ ， $x + 2 * n$ 和 $y + n$ 在同一个集合中,说明该条语句是错误的

如果输入的数据是 $2 x y$ ，说明 $x$ 吃 $y$ ，那么 $x$ 和 $y$ 必然不能是同一类，也就是 $(x ， y)$ , $(x + n, y + n)$ ， $(x + 2 * n, y + 2 * n)$ 不能在同一个集合中，另外也不存在A类吃C类，B类吃A类的情况，所以也要排除

别忘了x和y不能比n大，x不能等于y~

Code：

#include<bits/stdc++.h>
using namespace std;
int n,k,fa[150005],cnt;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void un(int a,int b){
    int aa=find(a);
    int bb=find(b);
    if(aa!=bb){
        fa[aa]=bb;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    for(int i=0;i<k;i++){
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if(d==1){
            if(find(x)==find(y+n)||find(x)==find(y+n+n)){
                cnt++; continue;
            }
            if(x>n||y>n){
                cnt++;continue;
            }
            un(x,y);
            un(x+n,y+n);
            un(x+n+n,y+n+n);
        }else if(d==2){
            if(find(x)==find(y)||find(x+n)==find(y+n)||find(x+n+n)==find(y+n+n)||find(x)==find(y+2*n)){
                cnt++;continue;
            }
            if(x>n||y>n||x==y){
                cnt++;continue;
            }
            un(x,y+n);
            un(x+n,y+2*n);
            un(x+2*n,y);
        }
    }
    printf("%d",cnt);
}