以前看到的做法是普通并查集开三倍内存，并没有怎么看懂。
现在用带权并查集看起来稍微直观一些。
这个题中物种只给出了相对关系，而带权并查集就是用来处理相对关系的。
注意：cin+优化依然会t，还是老老实实scanf吧 ==
转载解析：https://blog.csdn.net/yjr3426619/article/details/82315133 写的很好的一篇，里面有带权并查集的详解
1 #include<iostream> 2 using namespace std; 3 int n,k,f[50050],s[50010],ans; 4 5 void ini(){ 6 for (int i=1;i<=n;i++){ 7 f[i]=i; 8 s[i]=0; 9 } 10 ans=0; 11 } 12 13 int getf(int u){ 14 if (u!=f[u]){ 15 int tmp=f[u]; 16 f[u]=getf(f[u]); 17 s[u]=(s[u]+s[tmp])%3; 18 } 19 return f[u]; 20 } 21 22 inline void merge(int u,int v,int w){ 23 int uf=getf(u); 24 int vf=getf(v); 25 if (uf!=vf){ 26 f[uf]=vf; 27 s[uf]=(-s[u]+w+s[v]+3)%3; 28 return; 29 } 30 if ((w+s[v])%3!=s[u]) ans++; 31 } 32 33 int main() 34 { 35 cin>>n>>k; 36 ini(); 37 while (k--){ 38 int w,u,v; 39 scanf("%d %d %d",&w,&u,&v); 40 w--; 41 if (w==1 && u==v || u>n || v>n){ 42 ans++; 43 continue; 44 } 45 merge(u,v,w); 46 } 47 cout<<ans<<endl; 48 return 0; 49 }
原文：https://www.cnblogs.com/whiteli/p/12852942.html