class ConnectingGraph3 {
public:
ConnectingGraph3(int n) {
parent.reserve(n+1);
for(int i = 1; i <= n; i++) {
parent[i] = i;
}
setNumber = n;
}
int find(int node) {
if(node == parent[node]) {
return node;
}
parent[node] = find(parent[node]);
return parent[node];
}
/**
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
void connect(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if(rootA != rootB) {
parent[rootA] = rootB;
--setNumber;
}
}
/**
* @return: An integer
*/
int query() {
return setNumber;
}
private:
vector<int> parent;
int setNumber;
};