Connecting Graph III

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:

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

这道题又比Connecting Graph多了一个求联通块总数，只需要多一个成员变量count来记录. 每次connect的时候总块数减一，query()的时候返回count就行了。

public class ConnectingGraph3 {
    
    public int[] father = null;
    int count;
    public ConnectingGraph3(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        for (int i = 0; i < n + 1; i++){
            father[i] = i;
        }
        count = n;
    }

    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_b] = root_a;
            count--;
        }
    }
        
    public int query() {
        // Write your code here
        return count; 
    }
    
    private int find(int a){
        if (father[a] == a){
            return a;
        }
        return father[a] = find(father[a]);
    }
}