题目链接添加链接描述 题意：中文题不表 解题思路：太经典了，说实话其中的向量偏移的思想减少了好多好多的代码量，不然可能需要使用16个if来判断，实际上，其中的findx函数使用的思想就是同向直接相加的感觉。 很多博文写的很好 代码参考博客 百度推荐第一条博客 向量偏移，再加上递归加权的思想。有点菜，不过加油。
#include<stdio.h> using namespace std; const int maxn = 5e4+9; int fa[maxn],d[maxn]; int n,k; int r[maxn]; int findx(int x) { if(fa[x]==x) return x; else{ int temp=findx(fa[x]); r[x]=(r[x]+r[fa[x]])%3; fa[x]=temp; return fa[x]; // return fa[x]=findx(fa[x]); } } int Union(int op,int x,int y) { int root1=findx(x); int root2=findx(y); if(root1==root2) { if((r[x]-r[y]+3)%3==op-1)return 0; return 1; } fa[root1]=root2; r[root1]=(r[y]-r[x]+op-1+3)%3;///这是网上大牛的方法，巨牛批 ///采用什么向量偏移的方法，我巨服，但是这样的算法思维太过精妙 ///我以后在做类似题目的时候不知道能不能想出来，先学习下，再看看 ///我的基础算法就是if判断 // if(op==1) // { // if(r[x]==1&&r[y]==2)///x吃祖先，y被吃，两人又是同类 // { // r[root1]=2; // } // else if(r[x]==1&&r[y]==1){ // r[root1]=0; // } // else if(r[x]==2) // } return 0; } int sum; int main() { scanf("%d%d",&n,&k); int sum=0; for(int i=1;i<=n;i++) { fa[i]=i,r[i]=0; } for(int i=1;i<=k;i++) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==2&&x==y) { sum++; continue; } if(x>n||y>n) { sum++; continue; } sum+=Union(op,x,y); } printf("%d\n",sum); return 0; }