Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning.

http://www.lintcode.com/en/problem/connecting-graph/

You need to support the following method: connect(a, b), add an edge to connect node a and node b. 2.query(a, b)`, check if two nodes are connected

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

解题：这道题非常经典的并查集模版。

public class ConnectingGraph {
    private int[] father = null;
    public ConnectingGraph(int n) {
        //初始化father数组
        father = new int[n + 1];
        for (int i = 1; i <= n; 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 root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
        }
    }

    public boolean query(int a, int b) {
        // write your code here
        int root_a = find(a);
        int root_b = find(b);
        return root_a == root_b;
    }
}