Friday, April 14, 2017

Connecting Graph III

public class ConnectingGraph3 {

    private int[] father;
    private int parts;
    public ConnectingGraph3(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        parts = n;
    }
    private int find(int 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;
            parts--;
        }
    }
       
    public int query() {
        // Write your code here
        return parts;
    }
}

No comments:

Post a Comment