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)

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