Connecting Graph III

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

Example

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

Analysis:

Use union-find. Whenever there is legit "connect" happens, total connected components decrease by one.

Answer:

public class ConnectingGraph3 {

    private int[] father = null;
    private int total = 0;
    public ConnectingGraph3(int n) {
        // initialize your data structure here.
        total = n;
        father = new int[n+1];
        for(int i=1; i<n+1; i++)
        {
            father[i] = i;
        }
    }

    private int find(int x)
    {
        if(father[x] == x)
        {
            return x;
        }
        return father[x] = find(father[x]);
    }

    public void connect(int a, int b) {
        // Write your code here
        int rootA = find(a);
        int rootB = find(b);
        if(rootA != rootB)
        {
            father[rootA] = rootB;
            total--;
        }
    }

    public int query() {
        // Write your code here
        return total;
    }
}