题目链接：1182-食物链 代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
int pre[50010];
int rankrr[50010];
const int maxn=50000;
using namespace std;
int findr(int x){
    int r;
    int t;
    t=pre[x];
    if(pre[x]==x)        return pre[x];
    r=findr(pre[x]);        //递归查找根节点 
    pre[x]=r;                //路径压缩 
    rankrr[x]=(rankrr[x]+rankrr[t])%3;        //改变子节点的权值
    printf("find......done\n"); 
    return r;
}
void merge(int x,int y,int d){
    printf("merge......done\n");
    int rx,ry;
    rx=findr(x);
    ry=findr(y);
    pre[rx]=ry;
    rankrr[rx]=(rankrr[y]-rankrr[x]+3+d)%3;
}
int main(){
    int fake=0;
    int n,k;
    int x,y,d;
    scanf("%d %d",&n,&k);
    int i;
    for(i=1;i<=maxn;i++){
        pre[i]=i;
        rankrr[i]=0;
    }
    while(k--){
        scanf("%d %d %d",&d,&x,&y);
        if((x>n||y>n)||(d==2&&x==y)){
            fake++;
            printf("fake++\n");
        }
        else{
            int fx=findr(x);
            int fy=findr(y);
            if(fx!=fy){
                merge(x,y,d-1);
            }else{
                if((rankrr[x]-rankrr[y]+3)%3!=d-1){
                    fake++;
                    printf("fake++\n");
                }
            }
        }
    }
    printf("%d\n",fake);
    return 0;
}

       首先这道题要弄明白的是题目中的“当前的话与前面的某些真的话冲突，就是假话”到底是什么意思。事实上，第一句话肯定是真的，因为假如第一句话是假的，那我们就没有可以判断第二句话真假的依据了。接下来要做的其实只是判断当前的话与上面的话是否冲突。要注意的是，如果当前描述下，x与pre[x]无确定的关系，即fx!=fy，则将当前说法看作是正确的来进行merge。如果有确定的关系，再根据(rankr[x]-rankr[y]+3)%3与d-1的关系来判断对错。如果两者不相等，则为错；否则，对。 那么，如何进行集合的划分呢？在这道题里，集合的划分依据不是是否为同类，而是“是否能确定两者之间的关系”。（“ 注意，这里不是根据x与father[x]是否是同类来划分。而是根据“x与father[x]能否确定两者之间的关系”来划分，若能确定x与father[x]的关系，则它们同属一个集合”，摘自题解）        在判断的时候，如果输入的两只动物不是附属于同一个根节点，及不能确定两者的关系，就进行merge，merge的时候还要更新被并入的那个集合（即新的子树）的根节点的权值（即他与新的根节点的关系）。再合并的时候，我们只需要进行根节点的权值更新，被并入的集合的子节点的权值通过findr（）顺带更新（这也是带权并查集的精髓和难点）        在这道题中，并查集并不是要体现层级关系。同一棵树中的各个节点之间其实只是平等的几何元素关系，而没有上下级关系（或者说上下级关系对这道题而言没用）