NC16884 食物链 [并查集]

题意

存在一个环形食物链，即a->b->c->a，给出m条语句，均为两个动物是同一种，或者a吃b，问有多少句是假的，先入为主，若两句冲突，第一句为真。

题解

使用并查集。
以每个动物自身等级为基准，设定所有其他动物的等级，具体表现就是：开n*3的数组，a代表a所在等级，a+n代表吃a的等级，a+n+n代表被a吃的等级。
将语句中同一等级的动物放到同一个集合中，比如，1吃2，则将1+n（被a吃的等级）和b放到同一集合来设定a与b在食物链中关系。
那么判断两动物a，b是否在同一等级，就只需看a+n与b，a+n+n与b是否在一个集合中。
判断两动物是否为a吃b的关系，就只需看a与b，a与b+n+n是否在同一集合中。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 10;
int fa[maxn * 3];                   //记录祖先节点

int fi(int x){                  //find函数寻找祖先
    return x == fa[x] ? x : fa[x] = fi(fa[x]);
}

void un(int x,int y){           //union函数建立两点关系
    int p = fi(x);
    int q = fi(y);
    if(p != q) fa[p] = q;
}

int main(){     //若a吃b，则a的等级与b+n等级相同
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    int cnt = 0;
    while(m--){
        int op,a,b;                     
        scanf("%d%d%d",&op,&a,&b);
        if(a<1||a>n||b<1||b>n) {        //数据范围错误
            cnt++; 
            continue;
        }
        if(op==2&&a==b){                //表示x吃x
            cnt++;
            continue;
        }
        if(op==1){                      
            if(fi(a)==fi(b+n)||fi(a)==fi(b+n+n)) cnt++; //若a和b不为同一种
            else {
                un(a,b);                                //将a，b设置为同一等级
                un(a+n,b+n);
                un(a+n+n,b+n+n);
            }
        }
        else if(op == 2){                              
            if(fi(a)==fi(b)||fi(a)==fi(b+n+n)) cnt++;
            else {
                un(a,b+n);                             //令a与b+1为同一等级
                un(a+n,b+n+n);
                un(a+n+n,b);
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}