public class ConnectingGraph3 {
private int[] father;
private int parts;
public ConnectingGraph3(int n) {
// initialize your data structure here.
father = new int[n + 1];
for (int i = 0; i < n; i++) {
father[i] = i;
}
parts = n;
}
private int find(int x) {
if (father[x] == x) return x;
father[x] = find(father[x]);
return father[x];
}
public void connect(int a, int b) {
// Write your code here
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
parts--;
}
}
public int query() {
// Write your code here
return parts;
}
}
No comments:
Post a Comment