前言
前幾天看到并查集的題目，竟然只會最簡單的并查集，看來帶權并查集和擴展域并查集還要是好好寫個筆記復習復習的，
時間復雜度
如果僅僅使用路徑壓縮的并查集，時間復雜度似乎并不是\(O(\alpha(n))\)，詳情見這里，
擴展域并查集
yxc給出了一種簡單易懂的理解擴展域并查集的方式：將并查集中的元素看成一個個條件，兩個元素在一個集合中的意義是：如果有一個條件，那么整個集合中的條件都成立，
我來形式化一點：并查集中的每一個元素都是一個陳述句\(p\)，每一個集合\(S\)都是一個命題：
\(如果p(p \in S)，那么q(q \in S,q\not=p)，\)
這樣就十分容易理解了，
例如：P2024 [NOI2001] 食物鏈
注：(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)，
判斷矛盾同理，
CODE
帶權并查集
我們維護一個點到根節點的“距離”（這個“距離”是根據題意抽象得出的，而非真實的距離），以得出該點與集合中其它點的關系，
通常，關系有幾種，距離就有幾種，具體地，如果有\(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），但是空間占用小，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/523202.html
標籤：其他
上一篇：記錄一些寶藏網站
下一篇：技術美術的職責