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.

Have you met this question in a real interview?

Yes

Example

5 // n = 5
query(1) return 1
connect(1, 2)
query(1) return 2
connect(2, 4)
query(1) return 3
connect(1, 4)
query(1) return 3

class ConnectingGraph2 {
public:

ConnectingGraph2(int n) {

// initialize your data structure here.

father.resize(n + 1);

size.resize(n + 1);

for (int i = 1; i <= n; ++i) {

father[i] = i;

size[i] = 1;

}

}



void connect(int a, int b) {

// Write your code here

int fa = findParent(a);

int fb = findParent(b);

if (fa != fb) {

father[fb] = fa;

size[fa] += size[fb];

}

}



int query(int a) {

// Write your code here

int fa = findParent(a);

return size[fa];

}



int findParent(int i) {

while (i != father[i]) {

i = father[i];

}

return i;

}



vector<int> father;

vector<int> size;

};