Lintcode 591. Connecting Graph III

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), an edge to connect node a and node b
2. query(), Returns the number of connected component in the graph

Example

Example 1:

Input:
ConnectingGraph3(5)
query()
connect(1, 2)
query()
connect(2, 4)
query()
connect(1, 4)
query()

Output:[5,4,3,3]

Example 2:

Input:
ConnectingGraph3(6)
query()
query()
query()
query()
query()


Output:
[6,6,6,6,6]

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 42 43 44 45 46 47 48 49

public class ConnectingGraph3 {     private int[] parents;     private int numOfCC;       public ConnectingGraph3(int n) {         parents = new int[n + 1];         numOfCC = n;           for (int i = 0; i <= n; i++) {             parents[i] = i;         }     }       public void connect(int a, int b) {         if (a > b) {             int temp = a;             a = b;             b = temp;         }           int rootA = find(a);         int rootB = find(b);           if (rootA != rootB) {             parents[rootB] = rootA;             numOfCC--;         }     }       public int query() {         return numOfCC;     }       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;     } }