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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

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;     } }