题目连接：http://poj.org/problem?id=1182
基础并查集,需要维护与根节点关系，解析见代码：
/* poj 1182 并查集 思路分析：让你分析这些话里面多少假的 只需要用一个并查集将已经给出的这些元素存起来 同时记录每个元素与他们根节点关系，如果根结点相同 但是关系不符合就是出现了矛盾。 关系有三种：同类 记为0 吃根节点 1 被根节点吃 2 这样也是为了与他给出的d关系一致 d-1就与我们规定的关系一致了 并查集的关键是路径压缩，在压缩路径的同时我们要更新与根节点关系 寻找根节点时，要一并将根节点之下的元素与新的根节点的关系着更新掉 relate[x]=(relate[x]+relate[fa[x]])%3 合并的时候要更新根结点之间的关系，这个关系用向量很容易找到 fx->fy=fx->x(-relate[x])+x->y(d-1)+y->fy(relate[y]) */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=50000+100; int father[maxn],relat[maxn];//关系数组，表明它与父节点的关系，0代表同类，1代表被父节点吃，2代表吃父节点 int n,k; int findroot(int x) { if(x==father[x]) return x; int oldfa=father[x]; father[x]=findroot(father[x]); relat[x]=(relat[x]+relat[oldfa])%3;//更新压缩路径后它与父节点的关系 return father[x]; } void merge(int d,int x,int y) { int fx=findroot(x); int fy=findroot(y); if(fx==fy) return; father[fx]=fy; relat[fx]=(relat[y]+d-relat[x]+3)%3; return; } bool istrue(int d,int x,int y) { if(x>n||y>n||((d==2)&&(x==y))) return false; int fx=findroot(x),fy=findroot(y); if(fx!=fy)//两者关系待定 return true; else { if(relat[x]==(relat[y]+(d-1))%3) return true; else return false; } } int main() { int d,a,b; scanf("%d%d",&n,&k); int ans=0; memset(relat,0,sizeof(relat)); memset(father,0,sizeof(father)); for(int i=1;i<=n;i++) { father[i]=i; relat[i]=0;//自己和自己是同类 } while(k--) { scanf("%d%d%d",&d,&a,&b); if(!istrue(d,a,b)) ans++; else merge(d-1,a,b); } printf("%d ",ans); }