从小白开始刷算法 并查集篇 leetcode.547

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind union = new UnionFind(isConnected.length);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    union.union(i, j);
                }
            }
        }
        return union.getCount();
    }
}
class UnionFind {
    int[] parent;
    int count;
    public UnionFind(int size) {
        parent = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    public void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        if (parentX != parentY) {
            parent[parentX] = parentY;
            count--;
        }
    }
    public int getCount() {
        return count;
    }
}