代码模板

1.创建并查集

初始化：每个节点都以自身作为父节点

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

2.find()

路径压缩：每次遍历到的点都直接连到根节点上，下一次遍历不用遍历整条链

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

3.union()

void union(int x, int y){
    //将y所在的集合，合并到x所在的集合
    p[find(y)] = find(x);
}

例题1：朋友圈

链接：LeetCode547.朋友圈

这是一道非常经典的并查集模板题
我们只需要遍历一遍数组，把处于同一个朋友圈内的学生全部合并到同一个集合中即可
统计朋友圈个数，只需要统计有多少个点指向自己(相当于集合中的代表元素)

Java代码：

class Solution {
    int[] p;
    int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    void union(int x, int y){
        p[find(y)] = find(x);
    }

    public int findCircleNum(int[][] M) {
        int n = M.length;
        p = new int[n];
        for(int i = 0; i < n; i++){
            p[i] = i;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i != j && M[i][j] == 1){
                    union(i,j);
                }
            }
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(p[i] == i) res++;
        }

        return res;
    }
}

例题2：岛屿数量

链接：LeetCode200.岛屿数量
思路：

遍历每个岛屿，如果碰到陆地，则向上下左右四个方向延伸，如果碰到陆地，则合并
这样可以保证扩展到的所有陆地都连成一片，如果单纯遍历每个岛屿的话，无法确定这个岛屿是否需要合并
为方便建立并查集，把二维数组的下标转换为一维数组下标，通常a[i][j]可以表示为a[i*m+j]，其中m为二维数组的列数
统计答案也只需要统计一个集合的代表元素即可

Java代码：

class Solution {
    int[] p;
    int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    void union(int x, int y){
        p[find(y)] = find(x);
    }

    int[] dx = {1,0,-1,0};
    int[] dy = {0,1,0,-1};

    public int numIslands(char[][] g) {
        int res = 0;
        int n = g.length, m = g[0].length;
        p = new int[n*m];
        for(int i = 0; i < n*m; i++){
            p[i] = i;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == '1'){
                    for(int k = 0; k < 4; k++){
                        int a = i + dx[k];
                        int b = j + dy[k];
                        if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '1'){
                            union(i * m + j, a * m + b);
                        }
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == '1' && p[i * m + j] == i * m + j) res++;
            }
        }

        return res;
    }
}

例题3：冗余连接

思路：

并查集的经典用途：判定图中是否有环
举例：1->2,2->3,3->4,4->1，如何判定有环？
利用并查集，将12合并，再将23合并，再将34合并，说明1,2,3,4是连通的，不需要1->4来保证连通性

Java代码：

class Solution {
    int[] p;

    int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    void union(int x, int y){
        p[find(y)] = find(x);
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        p = new int[n+1];
        for(int i = 1; i <= n; i++) p[i] = i;
        int[] res = new int[2];
        for(int i = 0; i < n; i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(find(a) != find(b)){
                union(a,b);
            }else{
                res[0] = edges[i][0];
                res[1] = edges[i][1];
            }
        }
        return res;
    }
}