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

Have you met this question in a real interview?

Yes

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

1. 衍生用处， 查询集合的数量

public class ConnectingGraph3 {
    /*
    * @param n: An integer
    */
    int[] father = null;
    int count;
    public ConnectingGraph3(int n) {
        // do intialization if necessary
        father = new int[n + 1];
        for (int i = 1; i < father.length; i++) {
            father[i] = i;
        }
        count = n;
    }

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

        return father[a] = find(father[a]);
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    public void connect(int a, int b) {
        // write your code here
        int root_a = find(a);
        int root_b = find(b);

        if (root_a != root_b) {
            father[root_a] = root_b;
            count--;
        }

    }

    /*
     * @return: An integer
     */
    public int query() {
        // write your code here
        return count;
    }
}