Friday, April 14, 2017

Connecting Graph II

public class ConnectingGraph2 {

    private int[] father;
    private int[] size;
    public ConnectingGraph2(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }
    //find the root and compress the path at the same time
    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;
            size[rootB] += size[rootA];
        }
    }
       
    public int query(int a) {
        // Write your code here
        int rootA = find(a);
        return size[rootA];
    }
}

No comments:

Post a Comment