Lintcode 589. Connecting Graph

Given n nodes in a graph labeled from 1 to n. 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 node a and node b`.
2. query(a, b), check if two nodes are connected

Example

Example 1:

Input:
ConnectingGraph(5)
query(1, 2)
connect(1, 2)
query(1, 3) 
connect(2, 4)
query(1, 4) 
Output:
[false,false,true]

Example 2:

Input:
ConnectingGraph(6)
query(1, 2)
query(2, 3)
query(1, 3)
query(5, 6)
query(1, 4)

Output:
[false,false,false,false,false]







Solution:
Union-find.

Code (Java):

public class ConnectingGraph {
    private int[] parents;
    public ConnectingGraph(int n) {
        parents = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            parents[i] = i;
        }
    }
    
    private int find(int a) {
        int x = a;
        while (x != parents[x]) {
            x = parents[x];
        }

        while (a != x) {
            int temp = parents[a];
            parents[a] = x;
            a = temp;
        }

        return x;
    }

    public void connect(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            parents[rootB] = rootA;
        }
    }

    public boolean query(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        return rootA == rootB;
    }
}