Givennnodes in a graph labeled from1ton. There is no edges in the graph at beginning.
You need to support the following method:
1.connect(a, b), an edge to connect node a and node b
2.query(a), Returns the number of connected component nodes which include nodea.
public class ConnectingGraph2 {
HashMap<Integer, DSNode> map = new HashMap<>();
public ConnectingGraph2(int n) {
for (int i = 1; i <= n; i++) {
makeNode(i);
}
}
public void connect(int a, int b) {
DSNode na = findGroup(map.get(a));
DSNode nb = findGroup(map.get(b));
if (na == nb) {// already connected;
return;
}
if (na.rank >= nb.rank) {// put nodeB under nodeA
nb.parent = na;
na.rank += nb.rank;
nb.rank = -1;
} else {// put node A under node B
na.parent = nb;
nb.rank += na.rank;
na.rank = -1;
}
}
public int query(int a) {
DSNode res = findGroup(map.get(a));
return res.rank;
}
private DSNode findGroup(DSNode n) {
DSNode parent = n.parent;
if (parent == n) {// root
return n;
}
n.parent = findGroup(n.parent);// compress path
return n.parent;
}
private void makeNode(int nodeValue) {
DSNode newNode = new DSNode(nodeValue);
newNode.rank = 1;
newNode.parent = newNode;
map.put(nodeValue, newNode);
}
}
class DSNode {
int val;
int rank;// node number
DSNode parent;
public DSNode(int v) {
val = v;
}
}