// Java

class UnionFind { 

private int count = 0; 

private int[] parent; 

public UnionFind(int n) { 

count = n; 

parent = new int[n]; 

for (int i = 0; i < n; i++) { 

parent[i] = i;

}

} 

public int find(int p) { 

while (p != parent[p]) { 

parent[p] = parent[parent[p]]; 

p = parent[p]; 

}

return p; 

}

public void union(int p, int q) { 

int rootP = find(p); 

int rootQ = find(q); 

if (rootP == rootQ) return; 

parent[rootP] = rootQ; 

count--;

}

}

# Python

def init(p): 

# for i = 0 .. n: p[i] = i; 

p = [i for i in range(n)]

def union(self, p, i, j): 

p1 = self.parent(p, i) 

p2 = self.parent(p, j) 

p[p1] = p2

def parent(self, p, i): 

root = i 

while p[root] != root: 

root = p[root] 

while p[i] != i: # 路径压缩 ?

x = i; i = p[i]; p[x] = root 

return root

//C/C++

class UnionFind {

public:

    UnionFind(vector<vector<char>>& grid) {

        count = 0;

        int m = grid.size();

        int n = grid[0].size();

        for (int i = 0; i < m; ++i) {

            for (int j = 0; j < n; ++j) {

                if (grid[i][j] == '1') {

                    parent.push_back(i * n + j);

                    ++count;

                }

                else {

                    parent.push_back(-1);

                }

                rank.push_back(0);

            }

        }

    }

//递归

    int find(int i) {

        if (parent[i] != i) {

            parent[i] = find(parent[i]);

        }

        return parent[i];

    }

    void unite(int x, int y) {

        int rootx = find(x);

        int rooty = find(y);

        if (rootx != rooty) {

            if (rank[rootx] < rank[rooty]) {

                swap(rootx, rooty);

            }

            parent[rooty] = rootx;

            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;

            --count;

        }

    }

    int getCount() const {

        return count;

    }

private:

    vector<int> parent;

    vector<int> rank;

    int count;

};

// JavaScript

class unionFind {

constructor(n) {

this.count = n;

this.parent = new Array(n);

for (let i = 0; i < n; i++) {

this.parent[i] = i;

}

}

find(p) {

let root = p;

while (parent[root] !== root) {

root = parent[root];

}

// 压缩路径

while (parent[p] !== p) {

let x = p;

p = this.parent[p];

this.parent[x] = root;

}

return root;

}

union(p, q) {

let rootP = find(p);

let rootQ = find(q);

if (rootP === rootQ) return;

this.parent[rootP] = rootQ;

this.count--;

}

}