并查集

并查集题型

「力扣」第 547 题：省份数量（中等）；

「力扣」第 684 题：冗余连接（中等）；

「力扣」第 1319 题：连通网络的操作次数（中等）；

「力扣」第 1631 题：最小体力消耗路径（中等）；

「力扣」第 959 题：由斜杠划分区域（中等）；

「力扣」第 1202 题：交换字符串中的元素（中等）；

「力扣」第 947 题：移除最多的同行或同列石头（中等）；

「力扣」第 721 题：账户合并（中等）；

「力扣」第 803 题：打砖块（困难）；

「力扣」第 1579 题：保证图可完全遍历（困难）;

「力扣」第 778 题：水位上升的泳池中游泳（困难）。

模板

class UnionFind{
    int[] parent;
    UnionFind(int len){
        parent = new int[len];
        for(int i = 0; i < len; i++)
            parent[i] = i;
    }

    void union(int a, int b){
        parent[find(a)] = find(b);
    }

    int find(int a){
        if(a != parent[a]) parent[a] = find(parent[a]);
        return parent[a];
    }