并查集.md

概念

并查集(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); // a 合并到 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]++;
        }
    }
};

题目

图论

• LeetCode 547. Friend Circles (medium)

• LeetCode 803. Bricks Falling When Hit (hard)

• LeetCode 1319. Number of Operations to Make Network Connected (medium)

• LeetCode 765. Couples Holding Hands (hard)

• LeetCode 684. Redundant Connection (medium)

岛屿问题

• LeetCode 200. Number of Islands (medium)

• LeetCode 695. Max Area of Island (medium)

简单集合合并

• LeetCode 128. Longest Consecutive Sequence (hard)

拓展阅读

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