【概述】

定義：帶權并查集即是結點存有權值信息的并查集。

適用：當兩個元素之間的關系可以量化，并且關系可以合并時，可以使用帶權并查集來維護元素之間的關系。

權值：帶權并查集每個元素的權通常描述其與并查集中祖先的關系，這種關系如何合并，路徑壓縮時就如何壓縮。

與并查集的區別：帶權并查集可以推算集合內點的關系，而一般并查集只能判斷屬于某個集合。

【實現】

帶權并查集只是在并查集中加入了一個 value[N] 數組，與之相應，在 Find 函數與 Union 函數中也有改變。

對于并查集中每一棵樹，設樹根距離為 0，以樹根為參考，每個結點的權值代表與根節點的距離。

合并兩個元素時，假設 A、B 屬于不同的樹，如果合并這兩棵樹，把 A 樹合并到 B 樹上，就需要給 A 樹跟他的根結點賦值，假設于 A、B 的權值 Wa、Wb，由于兩權值代表的都是與根結點的距離，分析可知，給根結點所賦的值=Wa-Wb+x。

此時，對于原來的結點 A，只更新了 A 與他的根結點的權值，因此其他結點的更新在查找中實現即可。

int Find(int x){if(father[x]==x)return x;int temp=father[x];father[x]=Find(father[x]);value[x]+=value[temp];//結點a到根的距離return father[x]; }int Union(int x,int y,int w){int a=Find(x);int b=Find(y);if(a==b)//如果當前兩點與之前距離有沖突if(dis[y]!=dis[x]+w)return 1;father[b]=a;dis[b]=dis[x]-dis[y]+w;//計算兩點距離return 0; }

【常見類型】

種類問題

種類統計問題比普通并查集新增一屬性，常用于表示它和 father[i] 的關系，例如：用 group[i] 表示和 father[i] 的關系，同類可以用 0 表示，其他兩種分別用 1 表示該結點被父節點吃，2 表示該節點吃父節點。

統計問題

統計問題一般是對某種屬性進行統計，新增一屬性，在路徑壓縮時執行即可，例如：cnt[x] += cnt[fa]

區間問題

區間問題一般是記錄某區間 [l,r] 的數據，此類問題需要對所有值統計設置相同的初值，但初值的大小一般沒有影響，對區間 [l, r] 進行記錄時，實際上是對 (l-1, r] 操作，即 l = l - 1（勢差是在 l-1 和 r 之間）?

總結

以上是生活随笔為你收集整理的树形结构 —— 并查集 —— 带权并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。