B站 并查集
int find_root(int x) { if(parent[x]==-1)return x; while(parent[x]!=-1) { x=parent[x]; } return x; } int hebing(int x,int y) { int a=find_root(x); int b=find_root(y); if(a==b)return 1; else {if(deep[a]>deep[b]) parent[b]=a; else if(deep[a]>deep[b]) parent[a]=b; else //x==y,随便加 { parent[a]=b; deep[y]++; } return 0; } }检验代码
#include <iostream> using namespace std; const int N=100; const int M=200; int parent[N],deep[N]; int n,m; struct edge { int u,v,next; }e[N]; int cnt,head[N]; void init() { for(int i=0;i<=N;i++) { parent[i]=-1; deep[i]=1; head[i]=-1; } cnt=0; } void add(int x,int y) { e[cnt].u=x; e[cnt].v=y; e[cnt].next=head[x]; head[x]=cnt; cnt++; } int find_root(int x) { if(parent[x]==-1)return x; while(parent[x]!=-1) { x=parent[x]; } return x; } int hebing(int x,int y) { int a=find_root(x); int b=find_root(y); if(a==b)return 1; else {if(deep[a]>deep[b]) parent[b]=a; else if(deep[a]>deep[b]) parent[a]=b; else //x==y,随便加 { parent[a]=b; deep[y]++; } return 0; } } int disjoin() { int ans=0; for(int i=0;i<cnt;i++) { int a=e[i].u; int b=e[i].v; int c=hebing(a,b); if(c)ans=1; } return ans; } int main() { init(); cin>>n>>m; int x,y; for(int i=1;i<=m;i++) { cin>>x>>y; add(x,y);//链式前向星来储存 } if(disjoin())cout<<"存在环"; else cout<<"不存在环"; return 0; } /* 有环 6 6 1 2 1 3 2 4 3 5 3 6 4 5 无环 6 5 1 2 1 3 2 4 3 5 3 6 */并查集能维护连通性、传递性，通俗地说，亲戚的亲戚是亲戚。
然而当我们需要维护一些对立关系，比如 敌人的敌人是朋友 时，正常的并查集就很难满足我们的需求。
这时，种类并查集就诞生了。
常见的做法是将原并查集扩大一倍规模，并划分为两个种类。
在同个种类的并查集中合并，和原始的并查集没什么区别，仍然表达他们是朋友这个含义。
考虑在不同种类的并查集中合并的意义，其实就表达 他们是敌人 这个含义了。
按照并查集美妙的 传递性，我们就能具体知道某两个元素到底是 敌人 还是 朋友 了。
至于某个元素到底属于两个种类中的哪一个，由于我们不清楚，因此两个种类我们都试试。
具体实现，详见 P1525 关押罪犯。
再来看本题，每个动物之间的关系就没上面那么简单了。
对于动物 x 和 y，我们可能有 x 吃 y，x 与 y 同类，x 被 y 吃。
但由于关系还是明显的，11倍大小、2 倍大小的并查集都不能满足需求，3 倍大小不就行了！
类似上面，我们将并查集分为 33 个部分，每个部分代表着一种动物种类。
设我们有 n个动物，开了 3n 大小的种类并查集，其中 1 ∼n 的部分为 A群系，n + 1∼2n 的部分为 B 群系，2n + 1 ∼3n 的部分为 C 群系。
我们可以认为 AA表示中立者，B 表示生产者，C 表示消费者。此时关系明显：A 吃 B，A 被 C 吃。
当然，我们也可以认为 B 是中立者，这样 C 就成为了生产者，A 就表示消费者。（还有 11种情况不提及了）
联想一下 2倍大小并查集的做法，不难列举出：当 A 中的 x 与 B 中的 y 合并，有关系 x吃 y；当 C 中的 x 和 C 中的 y 合并，有关系 x 和 y 同类等等……
但仍然注意了！我们不知道某个动物属于 A，B，还是 C，我们3 个种类都要试试！
也就是说，每当有 1 句真话时，我们需要合并 3 组元素。
容易忽略的是，题目中指出若 x 吃 y，y 吃z，应有 x 被 z 吃。
这个关系还能用种类并查集维护吗？答案是可以的。
若将 x 看作属于 A，则 y 属于 B，z 属于 C。最后，根据关系 AA 被 C 吃可得 x被 z 吃。
既然关系满足上述传递性，我们就能放心地使用种类并查集来维护啦。
#include<cstdio> int fa[300005]; int n,k,ans; inline int read() { int sum=0; char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar(); return sum; }//读入优化 int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; }//查询 int unity(int x,int y) { int r1=find(fa[x]),r2=find(fa[y]); fa[r1]=r2; }//合并 int main() { int x,y,z; n=read(),k=read(); for(int i=1;i<=3*n;++i) fa[i]=i; //对于每种生物：设 x 为本身，x+n 为猎物，x+2*n 为天敌 for(int i=1;i<=k;++i) { z=read(),x=read(),y=read(); if(x>n||y>n) {ans++; continue;} // 不属于该食物链显然为假 if(z==1) { if(find(x+n)==find(y)||find(x+2*n)==find(y)) {ans++; continue;} //如果1是2的天敌或猎物，显然为谎言 unity(x,y); unity(x+n,y+n); unity(x+2*n,y+2*n); //如果为真，那么1的同类和2的同类，1的猎物是2的猎物，1的天敌是2的天敌 } else if(z==2) { if(x==y) {ans++; continue;} //其实是废话但是可以稍微省点时间 if(find(x)==find(y)||find(x+2*n)==find(y)) {ans++; continue;} //如果1是2的同类或猎物，显然为谎言 unity(x,y+2*n); unity(x+n,y); unity(x+2*n,y+n); //如果为真，那么1的同类是2的天敌，1的猎物是2的同类，1的天敌是2的猎物 } } printf("%d\n",ans); return 0; }