public class ConnectingGraph2 {
private int[] father;
private int[] size;
public ConnectingGraph2(int n) {
// initialize your data structure here.
father = new int[n + 1];
size = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
size[i] = 1;
}
}
//find the root and compress the path at the same time
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;
size[rootB] += size[rootA];
}
}
public int query(int a) {
// Write your code here
int rootA = find(a);
return size[rootA];
}
}
No comments:
Post a Comment