并查集(Disjoint Set)-阿里云开发者社区

并查集(Disjoint Set)

2024-01-10 39

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 并查集(Disjoint Set)

基本用途

处理不相交集合(disjoint sets)的合并和查询问题
处理分组问题
维护无序二元关系

基本操作

MakeSet(s):

建立一个新的并查集，其中包含s个集合，每个集合里只有一个元素。

UnionSet(x, y):

把元素×和元素y所在的集合合并。

要求×和y所在的集合不相交，如果相交则无需合并。

Find(x):

找到元素×所在的集合的代表。

该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。

内部实现

每个集合是一个树形结构

每个结点只需要保存一个值:它的父结点

最简单的实现是只用一个int数组fa, fa[x]表示编号为x的结点的父结点

根结点的fa等于它自己

初始化 MakeSet

合并 UnionSet

查询 Find + 路径压缩

路径压缩

并查集本质上只关心每个结点所在的集合，不关心该集合对应的树形结构具体是怎样的而一个结点所在的集合由根结点确定

因此在Find(x)的同时把x和×的所有祖先直接连到根结点上，下一次就可以一步走到根了

并查集还有一个优化叫做按秩合并（合并时把较浅的树合并到较深的上面）或者启发式合并（合并时把较小的树合并到较大的树上面)

同时采用路径压缩＋按秩合并优化的并查集，单次操作的均摊复杂度为O(a(n))只采用其中一种，O(log(n))

α(n)是反阿克曼函数，是一个比 log(n)增长还要缓慢许多的函数，一般α(n)≤5，近似常数通常实现中为了简便，我们只使用路径压缩

代码实现

class DisjointSet
{
public:
    DisjointSet(int n)
    {
        fa = vector<int>(n, 0);
        for (int i = 0; i < n; i++)
            fa[i] = i;
    }
    int find(int x)
    {
        if (x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    void unionSet(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            fa[x] = y;
    }
private:
    vector<int> fa;
};

进阶版本代码,加入集合数量记录

class UnionFind{
public:
    int find(int x){
        int root = x;
        while(father[root] != -1){
            root = father[root];
        }
        while(x != root){
            int original_father = father[x];
            father[x] = root;
            x = original_father;
        }
        return root;
    }
    bool is_connected(int x,int y){
        return find(x) == find(y);
    }
    void merge(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        if(root_x != root_y){
            father[root_x] = root_y;
            num_of_sets--;
        }
    }
    void add(int x){
        if(!father.count(x)){
            father[x] = -1;
            num_of_sets++;
        }
    }
    int get_num_of_sets(){
        return num_of_sets;
    }
private:
    // 记录父节点
    unordered_map<int,int> father;
    // 记录集合数量
    int num_of_sets = 0;
};

实战

547.省份数量

https://leetcode.cn/problems/number-of-provinces/

class UnionFind{
public:
    int find(int x){
        int root = x;
        while(father[root] != -1){
            root = father[root];
        }
        while(x != root){
            int original_father = father[x];
            father[x] = root;
            x = original_father;
        }
        return root;
    }
    bool is_connected(int x,int y){
        return find(x) == find(y);
    }
    void merge(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        if(root_x != root_y){
            father[root_x] = root_y;
            num_of_sets--;
        }
    }
    void add(int x){
        if(!father.count(x)){
            father[x] = -1;
            num_of_sets++;
        }
    }
    int get_num_of_sets(){
        return num_of_sets;
    }
private:
    // 记录父节点
    unordered_map<int,int> father;
    // 记录集合数量
    int num_of_sets = 0;
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFind uf;
        for(int i = 0;i < isConnected.size();i++){
            uf.add(i);
            for(int j = 0;j < i;j++){
                if(isConnected[i][j]){
                    uf.merge(i,j);
                }
            }
        }
        return uf.get_num_of_sets();
    }
};

130.被围绕的区域

https://leetcode.cn/problems/surrounded-regions/

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        const int dx[4] = {-1, 0, 0, 1};
        const int dy[4] = {0, -1, 1, 0};
        fa = vector<int>(m * n + 1, 0);
        for(int i = 0; i <= m * n; i++) fa[i] = i;
        int outside = m*n;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if (board[i][j] == 'X') continue;
                for(int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
                        unionSet(num(i, j), outside);
                    }else {
                        if (board[ni][nj] == 'O')
                            unionSet(num(i, j), num(ni, nj));
                    }
                }
            }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'O' && find(num(i, j)) != find(outside))
                    board[i][j] = 'X';
    }
private:
    int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
    void unionSet(int x, int y) {
        x = find(x),y = find(y);
        if (x != y) fa[x] = y;
    }
    int num(int i, int j) {
        return i * n + j;
    }
    int m, n;
    vector<int> fa;
};

145.超市

https://www.acwing.com/problem/content/147/

给定N个商品，每个商品有利润p;和过期时间d; ( 1 ≤N,p;, d≤ 10000)

每天只能卖一个商品，过期商品不能再卖

求如何安排每天卖的商品，可以使收益最大

并查集维护时间的占用情况，找到“deadline之前最近的空闲日”

#include "bits/stdc++.h"
using namespace std;
pair<int, int> a[10000];
int n;
int fa[10001];
int find(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
            cin >> a[i].first >> a[i].second;
        sort(a, a + n);
        for (int i = 0; i <= 10000; i++)
            fa[i] = i;
        int ans = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            int profit = a[i].first;
            int day = a[i].second;
            int lastAvailableDay = find(day);
            if (lastAvailableDay > 0)
            {
                ans += profit;
                fa[lastAvailableDay] = lastAvailableDay - 1;
            }
        }
        cout << ans << endl;
    }
}

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习