并查集练习---poj 1182 食物链
经典的并查集题目。
主要是节点之间的关系的维护。
首先看路径压缩部分：
[cpp]
int find(int x)
{
if (fa[x]==x) return x;
int t=fa[x];
fa[x]=find(fa[x]);
r[x]=(r[x]+r[t])%3;
return fa[x];
}
这里要注意保存原来的父节点。
再看如何合并：
[cpp]
fx=find(x);fy=find(y);
if (fx!=fy)
{
fa[fy]=fx;
c--;
r[fy]=(r[x]-r[y]-c+6)%3;
}
自己可以枚举一些情况找找规律。至于为什么加6，是为了确保为正（由于-c，所以不能只加3）
最后是判断是否为真：
[cpp]
if (c==1) ans+=r[x]!=r[y];
else ans+=(r[x]-r[y]+3)%3!=1;
这样这到题就解决了。
作者：ascii991
补充：软件开发 , C++ ,
