並查集算法詳解

一、基本概念

並查集是一種處理不相交集合的算法，用於解決連接問題。它維護一個森林，每棵樹表示一個集合，樹的根節點表示該集合的代表元，即集合的標識符。並查集可以快速地處理兩個元素是否在同一集合中，以及合併兩個集合的操作。

二、基本操作

1. 查找(find)

查找操作是並查集最常用的操作，用於判斷兩個元素是否在同一集合中，就是判斷它們是否有相同的根節點。

// 查找操作
int find(vector& parents, int x) {
    if (parents[x] != x) {
        parents[x] = find(parents, parents[x]);
    }
    return parents[x];
}

在查找操作時，我們使用路徑壓縮優化，將x到根節點的路徑上的所有節點直接與根節點相連，以提高後續查找操作的效率。

2. 合併(union)

合併操作主要用於將兩個不相交的集合合併成一個集合，將一棵樹的根節點連接到另一棵樹的根節點上，此時新的根節點成為新集合的代表元。

// 合併操作
void merge(vector& parents, vector& ranks, int x, int y) {
    int px = find(parents, x), py = find(parents, y);
    if (px != py) {
        if (ranks[px]  ranks[py]) {
            parents[py] = px;
        } else {
            parents[px] = py;
            ranks[py]++;
        }
    }
}

在合併操作時，我們使用了秩(rank)優化，將較小的樹連接到較大的樹上，以防止樹的深度過大產生退化。

3. 初始化(initialize)

在使用並查集前，需要先對每一個元素建立自己的集合，即將每個元素的父節點指向自己。初始化過程可以使用以下代碼實現:

// 初始化操作
void init(vector& parents) {
    for (int i = 0; i < parents.size(); i++) {
        parents[i] = i;
    }
}

三、應用場景

1. 判斷圖中是否存在環

使用並查集可以判斷一個無向圖中是否存在環。對於每條邊(u,v)，我們查找u和v所在的集合，若它們在同一集合中，則說明存在環；否則，我們將它們合併為同一集合。

// 判斷無向圖是否存在環
bool hasCycle(vector<pair>& edges, int n) {
    vector parents(n);
    init(parents);
    for (auto& edge : edges) {
        int px = find(parents, edge.first), py = find(parents, edge.second);
        if (px == py) {
            return true;
        }
        merge(parents, px, py);
    }
    return false;
}

2. 等價關係判斷

使用並查集可以快速地判斷兩個元素是否等價，即它們是否在同一集合中。我們可以維護一個等價類集合，將同一等價類的元素合併到一個集合中，以便於後續處理。

// 判斷兩個元素是否等價
bool isEquivalent(vector<vector>& eqClasses, int x, int y) {
    for (auto& eqClass : eqClasses) {
        int px = find(eqClass, x), py = find(eqClass, y);
        if (px == py) {
            return true;
        }
    }
    return false;
}

// 將等價類合併
vector<vector> mergeEqClasses(vector<vector>& eqClasses, int x, int y) {
    vector newEqClass;
    for (auto& eqClass : eqClasses) {
        int px = find(eqClass, x), py = find(eqClass, y);
        if (px != py) {
            for (auto& e : eqClass) {
                if (find(eqClass, e) == px || find(eqClass, e) == py) {
                    newEqClass.push_back(e);
                }
            }
        }
    }
    if (newEqClass.empty()) {
        newEqClass.push_back(x);
        newEqClass.push_back(y);
        eqClasses.push_back(newEqClass);
    } else {
        for (auto& eqClass : eqClasses) {
            if (find(eqClass, x) != -1 || find(eqClass, y) != -1) {
                eqClass = newEqClass;
                break;
            }
        }
    }
    return eqClasses;
}

3. 連通性判斷

使用並查集可以快速地判斷一個圖是否是連通的。我們可以使用並查集維護所有的邊集合中的點，若最終所有點都在同一集合中，則說明圖是連通的。

// 判斷圖是否連通
bool isConnected(vector<pair>& edges, int n) {
    vector parents(n);
    init(parents);
    for (auto& edge : edges) {
        int px = find(parents, edge.first), py = find(parents, edge.second);
        merge(parents, px, py);
    }
    int root = find(parents, 0);
    for (int i = 1; i < n; i++) {
        if (find(parents, i) != root) {
            return false;
        }
    }
    return true;
}

四、總結

並查集是一種快速處理不相交集合的算法，其核心是查找和合併操作。在實際應用中，我們可以通過並查集判斷圖中是否存在環，判斷元素之間是否存在等價關係，以及判斷圖是否連通等。不同應用場景下，我們可以靈活地使用並查集的不同操作來解決問題。