第一行：咕咕咕。
第二行：我原以为并查集很简单的。原以为。因此我现在一看到说并查集“简单有趣”的博客就心情复杂（不排除对人家来说真的简单有趣）。（本博客下次更新会附送简单并查集缓解心情）
第三行：谁能想到一道并查集我花了两个晚上呢。
第四行：这道题需要多多复习，我现在也不是特别明白。
第五行：还是小白书友好一些。
第六行：真正的勇士，敢于wa题二十次。
并查集：快速判断两个或多个元素的关系，快速合并两个集合 基础的合并or查找父节点我就不写了（包括递归查找和while循环查找）
本题POJ1182：两种思路：一种类似于向量；另一种分作三个区间0 ~ n表示同类，n+1 ~ 2n表示被吃，2n+1 ~ 3n表示吃别的（白书给出的思想 所附代码为第一种思路（用相对关系来表示其关系） 会再抽个合适的时间去写一下白书的代码的（其实是学一下白书的代码，因为这个思路在关系合并那里还是不太明白 留个坑
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #define maxn 500005 using namespace std; //当前写法为按向量来写 int f[maxn]; int r[maxn];//一个表示父节点一个表示关系（同类 void init() { for(int i = 0; i < maxn; ++i) { f[i]=i; r[i]=0; } } int tofind(int x) { if(x==f[x]) return x; int a=f[x]; int b=x; x=tofind(f[x]); f[b]=x; r[b]=(r[a]+r[b])%3; return x; } void tojoin(int x,int y,int op) { int a=tofind(y); f[a]=tofind(x); r[a]=(3-r[y]+op-1+r[x])%3; } int main() { init(); int n,k; int ans=0; scanf("%d%d",&n,&k); for(int i = 0; i < k; ++i) { int x,y,op; scanf("%d%d%d",&op,&x,&y); if(x>n||y>n||(op==2&&x==y)) ans++; else { int r1=tofind(x); int r2=tofind(y);//未合并过即没有关系 if(r1==r2) { if(op==1) { if(r[x]!=r[y]) ans++; } else { if((3-r[x]+r[y])%3!=1) ans++; } } else { tojoin(x,y,op); } } } printf("%d\n",ans); return 0; }附几个很不错的题解（有空再看看： 添加链接描述 添加链接描述 添加链接描述 再附几个简单的并查集缓缓心情SDNU1351
