【數據結構】帶權並查集

• 2021 年 2 月 17 日
• 筆記
• 演算法筆記

目錄

• 簡介
• 詳細介紹
• 例題

簡介

顧名思義，就是在維護集合關係的樹中添加邊權的並查集，這樣做可以維護更多的資訊。

引入題目：//www.luogu.com.cn/problem/P2024
比如這道題，如果使用普通的並查集則無法處理，因為普通的並查集只能夠刻畫兩個物品是否屬於同一個集合。因此這時候就要使用能夠記錄更多資訊的帶權並查集。

在閱讀前，需要先掌握並查集的知識。

詳細介紹

結合題目講解：//www.luogu.com.cn/problem/P2024

對於一個物種（一類動物），如果存在它吃另一個物種的關係，則讓它的度數比另一個物種多 \(1\) 。更嚴格地說，我們記該物種為 a （並非題意中的A），另一個物種是 b，它們對應的度數為d[]，那麼有 \(d[a]=d[b]+1\) 。如圖：

那麼有了這樣的規定，便有如下性質：

• d[a]%3==d[b]%3 時，a，b是同一個物種。（操作1）
• ((d[a]-d[b])%3+3)%3==1 時，存在a吃b的關係。（這裡多次取模是為了保證左邊的值只可能為 \(0,1,2\) ）（操作2）

從上面的性質可以看出，兩個物種的關係與它們的模數（這題是 \(mod3\) ）余多少關係密切相關，因此接下來我們也會著重考察兩個數之間的這種關係。

利用度數以及並查集，即可將各種動物之間的關係刻畫清楚：

這裡依然對a，b進行討論，為了方便，我們記a的祖宗（根節點）為pa，b的祖宗（根節點）為pb。

• 若pa，pb不在同一個集合中：
  就進行並查集的合併操作，讓f[pa]=pb。可以看出，在合併的時候，仍然作為根節點的pb的度數還是 \(0\)，但是pa的度數需要作出調整，才能夠保證結點之間關係的正確。
  ① 如果a和b是同一個物種（操作1）：則有 d[pa]+d[a]=d[b]
  ② 如果a吃b（操作2）：則有 d[pa]+d[a]-d[b]=1（當然，右式等於 \(4,7,10\) 這樣的數也是可以的，我們只需找到 \(mod 3餘1\)的數 ）
  

• 若pa，pb在同一個集合中：
  類似於上面的討論，
  ① 如果a和b是同一個物種（操作1）：如果 ((d[a]-d[b])%3+3)%3!=0，則矛盾，這句話便是謊言。
  ② 如果a吃b（操作2）：如果 ((d[a]-d[b])%3+3)%3!=1，則矛盾，這句話便是謊言。

綜上，我們的討論將所有情況覆蓋了。

路徑壓縮：
根據並查集的性質，如果不進行路徑壓縮，時間複雜度將會退化到 \(O(N)\) 。因此帶權並查集也要進行路徑壓縮，那麼主要問題就是解決如何維護d[]（度數）的問題：
概括地說，就是在查詢到某個點的時候，在搜索它的祖宗時遞歸地求出路上所有結點的度數，那麼它的度數就是d[x]+=d[f[x]]。

如上圖，pa在一次操作中併入了pb。
而在另一次操作中，對a的進行了查詢（求祖宗），便有如下路徑壓縮的並更新d[]的過程：
遞歸地找出祖宗pb。
pa的祖宗就是pb，度數在合併的時候已經求出來了，所以更新 \(0\)。
c的父親節點是pa，合併的時候並沒有更新（因此記錄的是距離pa的度數），度數需要加上 \(d[pa]\)，然後進行路徑壓縮。

a的父親節點是c，在上一步更新了，所以度數加上 \(d[c]\) 即可，類似的，進行路徑壓縮。

（這裡可能有點難理解，不過只要記住：所謂的d[x]指的是節點x相對於它父節點的度數即可）

不理解的地方可以結合程式碼理解

放上程式碼：（很短的）

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5;

int f[N],d[N];

int find(int x){
    if(x!=f[x]){
        int root=find(f[x]);
        d[x]+=d[f[x]];
        f[x]=root;
    }   
    return f[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<N;i++) f[i]=i;
    
    int cnt=0;
    while(m--){
        int op,a,b;
        cin>>op>>a>>b;
        
        //2,3 judge
        if(a>n || b>n){
            cnt++;
            continue;
        }
        if(a==b && op==2){
            cnt++;
            continue;
        }
        
        int pa=find(a),pb=find(b);
        
        int t= op==2;
        if(pa==pb){
            if(((d[a]-d[b])%3+3)%3!=t) cnt++;
        }else{
            f[pa]=pb;
            d[pa]=t+d[b]-d[a];
        }
    }
    
    cout<<cnt<<endl;
    
    return 0;
}

例題

//www.acwing.com/problem/content/241/
分析：思路完全類似於食物鏈那題。

//init
for(int i=1;i<N;i++) f[i]=i;

int ans=m;
for(int i=1;i<=m;i++){
    int a,b;
    string op;
    
    cin>>a>>b>>op;
    a=get(a-1); b=get(b);
    
    int t= op=="odd";
    
    int pa=find(a),pb=find(b);
    
    if(pa==pb){
        if(abs(d[a]-d[b])!=t){
            ans=i-1;
            break;
        }
    }else{
        //merge
        f[pa]=pb;
        d[pa]=d[a]^d[b]^t;
    }
}

cout<<ans<<endl;

return 0;