并查集解决连通分量的问题

并查集

它适合于解决连通分量的问题，就是一个工具类。难点在于如何将原问题转化为图的动态连通性问题。
实现的关键点有3个：

• 用parent数组记录每个节点的父节点，相当于指向父节点的指针，所以parent数组内实际存储着一个森林。
• 用size记录每颗树的重量，目的是为了调用union后树依然保持平衡性，而不会退化成链表。
• 在find函数中进行路径压缩，保证任意树的高度维持在常树，使得union和connected函数的时间复杂度为O(1)

实现代码如下：

class UnionFind{
    public int count;
    public int[] parent;
    public int[] size;

    public UnionFind(int n){
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ)
            return;
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean connected(int p, int q){
        return find(p) == find(q);
    }

    public int find(int x){
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public int count(){
        return this.count;
    }
}

判定合法等式

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        //先让相等的字母形成连通分量
        for(String str : equations){
            if(str.charAt(1) == '='){
                char x = str.charAt(0);
                char y = str.charAt(3);
                uf.union(x - 'a', y - 'a');
            }
        }
        for(String str : equations){
            if(str.charAt(1) == '!'){
                char x = str.charAt(0);
                char y = str.charAt(3);
                //如果相等关系成立，就是逻辑冲突
                if(uf.connected(x - 'a', y-'a')){
                    return false;
                }
            }
        }
        return true;
    }
}

省份数量

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(isConnected[i][j] == 1){
                    uf.union(i, j);
                }
            }
        }
        return uf.count();
    }
}

这道题也有点类似岛屿数量，也可以选择用图的DFS来做：

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
        int n = isConnected.length;
        // 定义 boolean 数组标识顶点是否被访问
        boolean[] visited = new boolean[n];
        // 定义 cnt 来累计遍历过的连通域的数量
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 若当前顶点 i 未被访问，说明又是一个新的连通域，则遍历新的连通域且cnt+=1.
            if (!visited[i]) { 
                cnt++;
                dfs(i, isConnected, visited);
            }
        }
        return cnt;
    }

    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;

        // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(j, isConnected, visited);
            }
        }
    }
}