并查集习题-poj 1182 食物链
并查集练习---poj 1182 食物链
经典的并查集题目。
主要是节点之间的关系的维护。
首先看路径压缩部分:
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]; }这里要注意保存原来的父节点。
再看如何合并:
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)
最后是判断是否为真:
if (c==1) ans+=r[x]!=r[y]; else ans+=(r[x]-r[y]+3)%3!=1;这样这到题就解决了。