Leetcode 547. Number of Provinces

[Woodyiiiiiii]

典型的并查集算法。

重新理解下：维护一个根数组f，每个元素代表该位置的根节点。一开始初始化每个位置都是自己的根节点，方便理解的话初始化为f[i] = i；接着，写一个寻找根节点方法find(int)，递归调用，直至f[i]=i，过程中可以赋值；最后，判断两个节点是否是一个集合，分别调用find(int)方法判断是否相等即可，若不相等，进一步可以对根节点改成另一个节点的根节点，实现是f[find(i)]=find(j)。

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 = 0; j < n; ++j) {
                if (isConnected[i][j] == 1) {
                    uf.connect(i, j);
                }
            }
        }
        
        return uf.getProvince();
    }
}

class UnionFind {
    
    int n;
    
    int[] f;
    
    public UnionFind(int n) {
        this.n = n;
        f = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
    }
    
    private int find(int i) {
        return f[i] == i ? f[i] : (f[i] = find(f[i]));
    }
    
    public void connect(int i, int j) {
        int fx = find(i);
        int fy = find(j);
        if (fx != fy) {
            f[fx] = fy;
        }
    }
    
    public int getProvince() {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            set.add(find(i));
        }
        return set.size();
    }
    
}

---

参考资料：

• 547. Number of Provinces