關于并查集

何為并查集

簡單來說，就是需要對集合進行操作，包括：確認一個元素屬于哪一個集合（或判斷兩個元素是否在同一個集合中）、合并兩個集合；

而能做到以非常快的速度完成上面兩個操作的數據結構就是————可以快速合并、查詢的集合，簡稱 “并查集”

模版

下面是并查集的模版題：洛谷 P3367 【模板】并查集（難度：提高-）
我們借助這道題目進行對并查集的講解

題目描述

如題，現在有一個并查集，你需要完成合并和查詢操作。

## 輸入格式
第一行包含兩個整數 \(N,M\) ,表示共有 \(N\) 個元素和 \(M\) 個操作。
接下來 \(M\) 行，每行包含三個整數 \(Z_i,X_i,Y_i\) 。
當 \(Z_i=1\) 時，將 \(X_i\) 與 \(Y_i\) 所在的集合合并。
當 \(Z_i=2\) 時，輸出 \(X_i\) 與 \(Y_i\) 是否在同一集合內，是的輸出
`Y` ；否則輸出 `N` 。

## 輸出格式
對于每一個 \(Z_i=2\) 的操作，都有一行輸出，每行包含一個大寫字母，為 `Y` 或者 `N` 。

## 數據范圍：
對于 \(100\%\) 的數據，\(1\le N\le 2\times 10^5\)，\(1\le M\le 10^6\)，\(1 \le X_i, Y_i \le N\)，\(Z_i \in \{ 1, 2 \}\)。

WriteUp

并查集的時間復雜度為 \(\Theta(\alpha(n))\) ，將其換為大O標記，就是平均復雜度；
這里的 \(\alpha(n)\) 為反阿克曼函數，增長極其緩慢，可以認為一般小于4，也就是常數級；

這里先講講并查集是如何做到快速操作的：
對于每個集合，并查集都選取一個代表元素，簡稱代表元，對于查詢兩個元素是否在同一個集合中的操作，只需要看看這兩個元素所在集合的代表元是否一樣即可；

那么如何找代表元呢：
當每個元素各自屬于一個集合時，他們的代表元為自己，記為 \(w_x\) ；
若一個集合中有不止1個元素，證明這個集合是由另外的集合合并過來的，因此現在的問題轉換成了：合并時如何修改代表元；

每次當我們合并兩個集合時（注意：也包括上面單一元素的情況），我們只需要將一個集合中所有元素的代表元設為另一個集合的代表元即可，現在請讀者思考一下這樣做的時間復雜度是多少；
顯然，是線性的，即 \(O(n)\) 級別，但是我們注意到，查詢操作是 \(O(1)\) 的，這提示我們，通過提高查詢操作的時間，有可能能夠降低合并操作的時間；

這里補充一點樹的知識：眾所周知，樹的一枝上會有分叉，分叉之后可能會有葉，也可能再分叉，我們如果將分叉點和葉都抽象成點，那么緊跟著一個分叉點的葉和這個分叉點就有“父子關系”，稱分叉點為葉節點的直接父親（直接前驅），葉節點稱為子節點，分叉點稱為父節點；

還記得何為 \(w_x\) 嗎，我們定義為元素 \(x\) 所在集合的代表元；
我們修改一下： \(w_x\) 為元素 \(x\) 的直接父親，特別的，當這個元素為某個集合的代表元時，它的直接父親為它自己；

每次合并時，我們先令一個集合為父，另一個為子，找到父集的代表元，將子集的代表元的直接父親設為父集代表元；
打個比方：如果小A是B的員工，現在B所在部門要合并到C的部門，那么B的上司為C，C自然也是A的一個領導了；
這里A、B的所在集合的代表元就是B，而與C合并時直接將B的父親設為C，自然A也屬于C了；

下一個問題是：如何尋找一個集合的代表元：

我們定義： \(find(x)\) 為尋找一個元素所在集合的代表元的函數，顯然，當 \(w_x = x\) 時，就找到了代表元，因為根據定義，只有代表元的父節點是其本身；
現在我們還是回到剛才的比喻：小A現在想找到管自己的最大的一個人，它就先找了B，問了B同樣的問題，B又去找了自己的頂頭上司C，C發現自己就是最大的，于是告訴B，B告訴A，小A就知道了；
所以當 \(w_x \not= x\) 時，我們就需要對父節點繼續進行 \(find(x)\) 這個操作，直到找到了代表元；

如果讀者比較細心，就會發現，目前的復雜度仍然不是常數級，在每次合并時，都需要進行一次 \(find(x)\) ，而 \(find(x)\) 的復雜度是跟深度有關的（比如小A有100個上司，那么查找自己的總經理的詢問次數就是100次），是 \(O(n)\) 線性級；

所以，目前的并查集仍然不是完全體，我們需要進一步優化；
如果我們在小A得到了自己的總經理是C這個結果之后，直接讓小A的父節點為C，那么下次小A的下級（如果有的話）詢問自己的總經理是誰是，就能跳過B這一步，直接從小A這里得到了答案；
更一般的，我們如果小A到C之間有100個人，當小A詢問完之后，讓這里每一個人的父節點都是C，那么下次任何一個人詢問的成本都將是1次，常數級，這就是我們想要的；
也就是大名鼎鼎的————“并查集之路徑壓縮”

具體的講，就是每次執行 \(find(x)\) 這個操作時，我們把所有節點的父節點都設為代表元，這樣下一次的合并操作就是 \(O(1)\) 的；
當然，第一次執行 \(find(x)\) 這個操作時沒有這種優化效果；

我們回到最開始的問題：
我們需要并查集能夠在常數時間內完成：1.合并兩個元素所在集合 2.判斷兩個元素是否在同一個集合中；
現在顯然，1我們已經通過代表元和路徑壓縮做到了，那么2呢；（這里如果讀者反應過來了，可以略過）
對于2，我們只需要判斷 \(find(x)\) 是否等于 \(find(y)\) ，就OK了；
而 \(find(x)\) 在路徑壓縮下是近似 \(O(1)\) 的，所以，全部的目標達成；

下面給出C++的代碼：

#include<iostream>
using namespace std;
const int MAXN = 2e5+7;
int fa[MAXN];
int n,m;
int op,u,v;
int find(int x){
    if(fa[x]==x) return x; //找到了代表元
    fa[x] = find(fa[x]);   //詢問父節點，并將代表元設為詢問節點的父節點
    return fa[x];
}
void union_set(int x,int y){
    int p = find(x),q = find(y);
    fa[q] = p;    //將y所在集合的代表元的父節點設為x所在集合的代表元
}
bool if_same(int x,int y){
    return find(x)==find(y);
}
/*
  初始化函數，參數為元素數量；
*/
void init(int x) {
    for (int i=1;i<=x;i++) {
        fa[i] = i;
    }
}
int main() {
    cin>>n>>m;
    init(n);
    for(int i=0;i<m;i++) {
        cin>>op>>u>>v;
        if (op==1) union_set(u,v);
        else {
            bool tmp = if_same(u,v);
            if (tmp) {
                cout<<"Y"<<endl;
            }else {
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}

一些補充：

1.反阿克曼函數的增長真的非常非常慢，在操作數 \(N \le 10^{18}\) 的情況下都小于4
2.平均復雜度的說法是不嚴謹的，應該是均攤復雜度接近常數級
3.這里沒有提到“按秩合并”的方法，在一般情況下，路徑壓縮的算法已經很優，再使用按秩合并意義不大，不過如果是OI競賽，建議帶上，這里受限于篇幅，暫不介紹

不過提一嘴：所謂的秩，就是樹的高度，當合并兩個集合時，將樹矮的集合并到樹高的集比較好，具體原因可以想想有100個上司的小A
實現很簡單，增加一個輔助數組即可；

4.find函數在遞歸深度比較大時可能爆棧，可以改成循環實現，也很簡單；

結語&一些題目：

“命運要靠自己來把握”————《強風吹拂》

并查集的題目：https://www.luogu.com.cn/training/3065#problems
相當一部分是模版題，歡迎挑戰

如有筆誤，歡迎指正，不吝賜教

posted @ 2025-08-24 21:57 Ghost-Face 閱讀(128) 評論(0) 收藏舉報

刷新頁面返回頂部

GhostFace的Blogs