並查集練習---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; 
這樣這到題就解決了。