Union Find 模板

class Solution {

    class UnionFind {
        private int[] root;
        private int[] rank;
        private int count;

        UnionFind(int size) {
            root = new int[size];
            rank = new int[size];
            count = size;
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

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

        void union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
                count--;
            }
        }
        
        // return count of joined sets
        int getCount() { return count; }
    }
    
    // Union Find
    public int findCircleNum(int[][] isConnected) {
        // some function...
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (something) {
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }
}

例题：https://app.gitbook.com/s/-L9mNqXfPqoVkVgLGF9r/bfs/islands/547.-number-of-provinces