并查集算法详解

小蓝 • 2024-11-18 20:00 • 编程

一、基本概念

并查集是一种处理不相交集合的算法，用于解决连接问题。它维护一个森林，每棵树表示一个集合，树的根节点表示该集合的代表元，即集合的标识符。并查集可以快速地处理两个元素是否在同一集合中，以及合并两个集合的操作。

二、基本操作

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;
}

四、总结

并查集是一种快速处理不相交集合的算法，其核心是查找和合并操作。在实际应用中，我们可以通过并查集判断图中是否存在环，判断元素之间是否存在等价关系，以及判断图是否连通等。不同应用场景下，我们可以灵活地使用并查集的不同操作来解决问题。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/157475.html