並查集總結
前言
前幾天看到並查集的題目，竟然只會最簡單的並查集，看來帶權並查集和擴展域並查集還要是好好寫個筆記複習複習的。
時間複雜度
如果僅僅使用路徑壓縮的並查集，時間複雜度似乎並不是\(O(\alpha(n))\)，詳情見這裡。
擴展域並查集
yxc給出了一種簡單易懂的理解擴展域並查集的方式：將並查集中的元素看成一個個條件，兩個元素在一個集合中的意義是：如果有一個條件，那麼整個集合中的條件都成立。
我來形式化一點：並查集中的每一個元素都是一個語句\(p\)，每一個集合\(S\)都是一個命題：
\(如果p(p \in S)，那麼q(q \in S,q\not=p)。\)
這樣就十分容易理解了。
註：(x)指並查集中編號為x的元素。
我們定義：
- (x)表示第x個動物是A
- (x+n)表示第x個動物是B
- (x+2n)表示第x個動物是C
這樣動物之間的關係就十分清晰了，合併的時候只需滿足題意即可。
x和y同類：
- 如果(x)，那麼(y)；如果(x+n)，那麼(y+n)；如果(x+2n)，那麼(y+2n)。
x吃y：
由於A吃B，B吃C，C吃A，所以：
- 如果(x)，那麼(y+n)；如果(x+n)，那麼(y+2n)；如果(x+2n)，那麼(y)。
判斷矛盾同理。
帶權並查集
我們維護一個點到根節點的「距離」（這個「距離」是根據題意抽象得出的，而非真實的距離），以得出該點與集合中其它點的關係。
通常，關係有幾種，距離就有幾種，具體地，如果有\(n\)種關係，就有\(n\)種距離，為了方便，一般將距離定義為\([0,n-1]\)，這樣可以使用取模運算方便地得出兩點間相對關係。
還是上面的例題，這次使用帶權並查集來做。
兩隻動物之間的關係只有3種，所以我們定義距離：
- 0：與根節點同類
- 1：被根節點吃
- 2：吃根節點
註：x->y意為x吃y
紅色的邊是根據題意的環形結構推理得出的。
所以，我們會發現當且僅當\(d_x + 1 \equiv d_y (mod 3)\)時，x吃y。
同類自然就不用講，只要\(d_x \equiv d_y(mod 3)\)，x和y就同類。
判斷矛盾同理。
維護\(d_x\)時，只需要暴力維護到根的權值之和即可。這為何是正確的呢？直觀地理解，每一個結點都吃更深一層的結點，到了第3層，剛好完成一個循環，也就是第3層的結點和第0層的是同類，
而我們判斷關係時又是在同餘下處理的，所以自然是正確的。
需要注意的是，如果不做特殊處理，直接累加距離的話，可能會導致距離倍增並溢出。
解決辦法有兩個：
- 對\(d_x\)取模；
- 在更新\(d_x\)時，只累加\([0,n-1]\)的值（正餘數）。
對比
擴展域並查集更加直觀、易懂，不易寫錯，但是也有缺點，就是空間佔用過多。
帶權並查集關係較為複雜，用到了同餘的知識，可能會吃數學的虧（like me），但是空間佔用小。
