带权并查集就是除了维护一个fa数组以外，维护一个rank数组，有两层含义，一个是路径压缩时边的权值，，再一个是当前点与根节点的相对关系。这个题很明显考察的是
根节点与当前节点的一种相对关系，让rank【x】 = 0 ，1，2表示A，B，C三个种类的动物，在刚开始的时候，所有的动物的rank值都是0，表示还没有给他们安排关系，随
着语句的输入，1xy表示把x,y置为相同值，2xy表示rank【x】 + 1 = rank【y】，然而在这里并不是直接改变y的rank的值，而是改变y所在的根结点的rank值，因为一旦x,y确
立了关系，和y在一个集合内的动物都与x建立了关系，这样只有改变根节点的rank才能保证每一个动物的rank都会被更新到，因为在x所在的集合和y所在的集合没有建立关系
之前，x,y的关系可以是任意的。
如果输入1xy，首先看x,y是否在一个集合内，如果是那麽x,y之间是一种绝对的关系，可以通过rank【x】和rank【y】的大小来判断语句的正确性，如果不是那麽x,y之间就没有
确定的关系，那么这句话就是对的，修改rank【y】所在集合的根结点的rank值，
输入2xy时和输入1xy时同理。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<map> #define N 100005 #define lc rt<<1 #define rc rt<<1|1 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 5e4 + 10; int n,k; int d,x,y; int fa[maxn]; int rank[maxn]; int find(int x) { if(fa[x] == x) return x; int p = find(fa[x]); rank[x] = (rank[fa[x]] + rank[x])%3; return fa[x] = p; } int main() { //freopen("in","r",stdin); int cnt = 0; scanf("%d%d",&n,&k); for(int i = 0; i < n; ++i) fa[i] = i; memset(rank,0,sizeof(rank)); for(int i = 0; i < k; ++i) { scanf("%d%d%d",&d,&x,&y); if(x > n||y > n||(d == 2&&x == y)) { cnt++;continue;} int s1 = find(x),s2 = find(y);//求根节点 if(d == 1){ if(s1 == s2){ if(rank[x] != rank[y]) cnt++; } else { rank[s2] = (rank[x] - rank[y] + 3)%3;//更新y的根结点，注意不要写错s2； fa[s2] = s1;//建立x集合与y集合的关系； } } else if(d == 2) { if(s1 == s2) { if((rank[x] + 1)%3 != rank[y]) cnt++; } else { rank[s2] = (rank[x] + 1 - rank[y] + 3)%3;//同上 fa[s2] = s1; } } //printf("%d %d ",i,cnt); } printf("%d ",cnt); }