Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning. You need to support the following method: connect(a, b), an edge to connect node a and node b query(), Returns the number of connected component in the graph Example

Example 1:
Input:
ConnectingGraph3(5)
query()
connect(1, 2)
query()
connect(2, 4)
query()
connect(1, 4)
query()

Output:[5,4,3,3]

Example 2:
Input:
ConnectingGraph3(6)
query()
query()
query()
query()
query()

Output:[6,6,6,6,6]

public class ConnectingGraph3 {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    private int[] father = null;
    private int count = 0;

    public ConnectingGraph3(int n) {
        father = new int[n+1];
        count = n;
        for(int i = 1; i < n+1; i++) { //初始化各点，老大哥都指向自己
            father[i] = i;
        }
    }

    //找到老大哥
    private int find(int x) {
        List<Integer> path = new ArrayList<>();
        while(father[x] != x) {
            path.add(x);
            x = father[x];
        }

        for(Integer i : path) { //把路径上所有点都指向老大哥
            father[i] = x;
        }

        return x;
        // if(father[x] == x) return x;
        // father[x] = find(father[x]);
        // return 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;
            count--;
        }
    }

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

不用array用hashmap做
public class ConnectingGraph3 {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    private Map<Integer, Integer> father = new HashMap<>();
    private int count = 0;

    public ConnectingGraph3(int n) {
        count = n;
        for(int i = 1; i < n+1; i++) { //初始化各点，老大哥都指向自己
            father.put(i, i);
        }
    }

    //找到老大哥
    private int find(int x) {
        List<Integer> path = new ArrayList<>();
        while(father.get(x) != x) {
            path.add(x);
            x = father.get(x);
        }

        for(Integer i : path) { //把路径上所有点都指向老大哥
            father.put(i, x);
        }

        return x;
    }

    //合并时候合并两个老大哥
    public void connect(int a, int b) {
        // write your code here
        int rootA = find(a);
        int rootB = find(b);
        if(rootA != rootB) {
            father.put(rootA, rootB);
            count--;
        }
    }

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