并查集是一种支持集合合并和查询的数据结构

概念

并查集(Union-Find Set),也称为不相交集数据结构(Disjointed Set Data Structure), 指一系不相交的集合(Sets),提供合并(Union)和查找(Find)两种操作。

总结:一种用来 解决集合查询合并 的数据结构,支持 近乎O(1)的find操作近乎O(1)的union操作

两个基本操作

  • find(int i)

    判断是否属于同一集合 find(i)即查找I所归属的集合,通常我们使用find(i)和find(j)判断i和j是否连通,即是否属于同一个集合

  • union(int i , int j)

    将两个集合进行合并 顾名思义,union方法即将I和J所在的两个集合连通起来,执行这个方法后,I所在集合和所有元素和J所在集合的所有元素都连通

可以解决的问题(适用场景)

有N个点,用M条线进行两两相连的操作(相连即为合并操作)

  1. 问A点和B点是否连通

    判断 find(A) == find(B)

  2. 问连通块的总个数

    for i:0~n
      cnt+= i != find(i)
    
  3. 问A点所在连通块的节点个数

    for i:0~n;
        find(A) == find(i) && cnt++
    
  4. 判断是否存在环路

    进行合并操作时,先判断是否连通,如果已经连通,则存在环路,此时进行合并会死循环

代码模板

初始化

for (int i = 0; i< n ; i++) p[i] = i;

查找find

int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]); // 带路径压缩
}

合并Union

老大哥之间合并,跟小弟没关系

void unionA(int a, int b){
    p[find(a)] = find(b);
}

完整版代码

int f[N];

for (int i = 0; i < n; i++)f[i] = i; // 构造

int find(int x) { // 查询
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

void u(int x, int y) { // 合并; 当find(x) != find(y) 才进行合并; 如果find(x) == find(y),没必要进行合并,已经在一个集合;此时进行合并表明存在环路;
    f[find(x)] = find(y);
}

bool isOneSet(int x, int y) return find(x)==find(y);

带rank的路径压缩实现(了解)

class Solution {
public:
    void makeSet(int n){
        vector<int> p(n, 0);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        vector<int> rank(n, 0);
    }

    int find(vector<int> &p, int x) {
        if (p[x] != x) {
            p[x] = find(p, p[x]);  //路径压缩
        }
        return p[x];
    }

    void unionSet(vector<int> &p, vector<int> &rank, int x, int y) {
        x = find(p, x);
        y = find(p, y);
        if (rank[x] < rank[y]) p[x]= y;
        else {
            p[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }
};

题目

图论

岛屿问题

拓展阅读

  • 算法导论-第21章:用于不想交集合的数据结构