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(a), Returns the number of connected component nodes which include nodea.

Have you met this question in a real interview?

Yes

Example

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

1. 衍生应用，查询所在集合的元素数量

public class ConnectingGraph2 {
    /*
    * @param n: An integer
    */
    int[] father = null;
    int[] nodes = null;
    public ConnectingGraph2(int n) {
        // do intialization if necessary
        father = new int[n + 1];
        nodes = new int[n + 1];

        for (int i = 1; i < father.length; i++) {
            father[i] = i;
            nodes[i] = 1;
        }
    }

    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;
            nodes[root_b] += nodes[root_a];
        }
    }

    /*
     * @param a: An integer
     * @return: An integer
     */
    public int query(int a) {
        // write your code here
        int root_a = find(a);

        return nodes[root_a];
    }
}