公认的并查集经典。题目不贴了，链接在这里http://poj.org/problem?id=1182
并查集的基础功能是 判断两个元素是否属于同一个集合 和 合并元素到同一个集合。
更高的层次的应用是 判断和维护两个元素的关系。
数组Fa[ x ]表示x所在集合的根节点，Rank[ x ]表示x和x所在集合根节点的关系。
这篇博客深入的解释了这道题目，图文并茂，强烈推荐
https://blog.csdn.net/niushuai666/article/details/6981689
向量的思想实在是惊艳，一下子就把这个问题完美的刻画出来。
题目说“动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A”。
这构成一个循环，与取模运算有很大的相似性。所以我们做出如下假设：
Rank[ x ]=0表示x和Fa[ x ]同类
Rank[ x ]=1表示Fa[ x ]吃x
Rank[ x ]=2表示Fa[ x ]被x吃
这样假设之后，关系就能够通过加减进行计算。
例如：
如果A吃B， B吃C，那么按照向量的计算，A和C的关系就是AB加BC，即AC=AB+BC,按照上面假设等于2，结果就是A被C吃
如果A吃B，A吃C，BC=AC-AB=0，B和C是同类
.......
这也解释了为什么输入的D要减一
代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #define DEBUG(x) cout<<#x<<" = "<<x<<endl using namespace std; const int MAXN=5e4+10; int N,K; int Fa[MAXN]; int Rank[MAXN]; ///Rank表示关系 ///0表示x和Fa[x]同类 ///1表示Fa[x]吃x ///2表示Fa[x]被x吃 int Find(int e) { if(Fa[e]==e)return e; int oldF=Fa[e]; Fa[e]=Find(Fa[e]); Rank[e]=(Rank[oldF]+Rank[e])%3; return Fa[e]; } void Union(int a,int b,int r) { int t1=Find(a); int t2=Find(b); if(t1!=t2){ Fa[t2]=t1; Rank[t2]=(Rank[a]+r+3-Rank[b])%3; } } void Init() { for(int i=0;i<=N ;i++ ){ Fa[i]=i; Rank[i]=0; } } int main() { // freopen("in.txt","r",stdin); int cnt=0; scanf("%d%d",&N,&K); Init(); while(K--){ int D,X,Y; scanf("%d%d%d",&D,&X,&Y); if(X>N||Y>N){cnt++;continue;} if(D==2&&X==Y){cnt++;continue;} int r1=Find(X); int r2=Find(Y); if(r1==r2){ if((Rank[Y]-Rank[X]+3)%3!=D-1)cnt++; } else { Union(X,Y,D-1); } } printf("%d\n",cnt); }
原文：https://www.cnblogs.com/MalcolmMeng/p/9519871.html