Number of Provinces

给一个无向图, 求几个强连通组件.

并查集的例题.

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int size = isConnected.length;
        DSU dsu = new DSU(size);
        for(int i = 0; i < isConnected.length; i++) {
            for(int j = 0; j < isConnected.length; j++) {
                if(isConnected[i][j] == 1){
                    dsu.union(i, j);
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < size; i++) {
            set.add(dsu.get(i));
        }
        return set.size();
    }
    class DSU{
        int[] p;
        public DSU(int size) {
            this.p = new int[size];
            for(int i = 0; i < size; i++) {
                p[i] = i;
            }
        }
        int get(int v) {
            if(p[v] == v)
                return v;
            return p[v] = get(p[v]);
        }
        boolean union(int a, int b) {
            a = get(a);
            b = get(b);
            if(a == b)
                return false;
            p[a] = b;
            return true;
        }
    }
}