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), add an edge to connect nodeaand node b. 2.query(a, b)`, check if two nodes are connected

Have you met this question in a real interview?

Yes

Example

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

1. 基本用处

a. 查询两元素是否在同一集合

b. 合并两个集合

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

    private int find(int n) {
        if (numbers[n] == n) {
            return n;
        }

        return numbers[n] = find(numbers[n]);
    }

    /*
     * @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) {
            numbers[root_a] = root_b;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: A boolean
     */
    public boolean query(int a, int b) {
        // write your code here
        return find(a) == find(b);
    }
}