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(), Returns the number of connected component in the graph

Have you met this question in a real interview?

Yes

Example

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

Tags

Union Find

class ConnectingGraph3 {

public:

ConnectingGraph3(int n) {

    // initialize your data structure here.

    parent.resize(n + 1);

    component = n;

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

        parent[i] = i;

    }

}



void  connect(int a, int b) {

    // Write your code here

    int pa = getParent(a);

    int pb = getParent(b);

    if (pa != pb) {

        parent[pb] = pa;

        component--;

    }

}



int query() {

    // Write your code here

    return component;

}
private:

vector<int> parent;

int component;

int getParent(int i) {

    int cur = i;

    while (cur != parent[cur]) {

        cur = parent[cur];

    }

    int parenti = parent[cur];

    while ( parent[i] != i) {

        int temp = parent[i];

        parent[i] = parenti;

        i = temp;

    }

    return parenti;

}
};