BiruLyu
6/22/2017 - 5:20 AM

## 547. Friend Circles.java

``````public class Solution {
public int findCircleNum(int[][] M) {
if (M == null || M.length < 1 || M[0].length < 1) return 0;
int n = M.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
uf.make_set(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (M[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.getCount();
}
}

class UnionFind {
private int[] parent;
private int[] size;
private int n, count;

public UnionFind (int n) {
this.n = n;
this.count = n;
parent = new int[n];
size = new int[n];
}

public void make_set(int x) {
parent[x] = x;
size[x] = 1;
}

public int find(int x) {
// if (parent[x] != x) {
//     parent[x] = find(parent[x]);
// }
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}

return x;
}

public void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if (parentX != parentY) {
if (size[parentX] > size[parentY]) {
parent[parentY] = parentX;
size[parentX] += size[parentY];
} else {
parent[parentX] = parentY;
size[parentY] += size[parentX];
}
count--;
}
}

public int getCount() {
return count;
}
}``````