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), add an edge to connect nodeaand node b. 2.query(a, b)`, check if two nodes are connected

Have you met this question in a real interview?

Yes

Example

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

name error line 13 not find, should be findParent;

missiong semicolon at line 26;

class ConnectingGraph {

public:

ConnectingGraph\(int n\) {

    // initialize your data structure here.

    pa.resize\(n + 1\);

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

        pa\[i\] = i;

    }

}



void  connect\(int a, int b\) {

    // Write your code here

    int a1 = find\(a\);

    int b1 = find\(b\);

    if \(a1 != b1\) {

        pa\[b1\] = a1;

    }

}



bool query\(int a, int b\) {

    // Write your code here

    return find\(a\) == find\(b\);

}



int find\(int i\) {

    int p = i;

    while \(p != pa\[p\]\) {

        p = pa\[p\];

    }

    int k = i;

    while \(k != pa\[k\]\) {

        int temp = pa\[k\];

        pa\[k\] = p;

        k = temp;

    }



    return p;

}

private:

vector<int> pa;

};