BiruLyu
6/22/2017 - 4:53 AM

## 323. Number of Connected Components in an Undirected Graph.java

``````public class Solution {
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
uf.make_set(i);
}
for (int i = 0; i < edges.length; i++) {
uf.union(edges[i][0], edges[i][1]);
}
return uf.getCount();
}
}

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

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

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

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 parent[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;
}
}
``````