Connecting Graph II - Lintcode

Givennnodes in a graph labeled from1ton. 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(a), Returns the number of connected component nodes which include nodea.

Example

5 // n = 5
query(1) return 1
connect(1, 2)
query(1) return 2
connect(2, 4)
query(1) return 3
connect(1, 4)
query(1) return 3

Analysis

Note that after connect, the components nodes of the connected should be combined together. 1st solution is to use a child array so that the connection is done from a root (node without any further father) and another (a child without another further decendants). 2nd solution is use a size array to record the number of the size in each connected component. The 2nd solution is simple and easy to implement while the first solution can be easily extended to support "disconnection".

1st solution

int[] child = null;
int[] father = null;

public ConnectingGraph2(int n) {
    child = new int[n + 1];
    father = new int[n + 1];

    for (int i = 0; i < n + 1; i++){
        child[i] = i;
        father[i] = i;
    }
}

public void connect(int a, int b) {
    int aFather = findFather(a);
    int bChild = findChild(b);
    if (!isConnected(bChild, aFather)){
        father[aFather] = bChild;
        child[bChild] = aFather;
    }
}

public boolean isConnected(int a, int b){
    if (father[a] == b){
        return true;
    } else if (father[a] == a){
        return false;
    }
    return isConnected(father[a], b);
}

public int query(int a) {
        int aChild = findChild(a);
        int aFather = findFather(a);

        if (aChild == aFather){
            return 1;
        }

        int count = 1;
        while (father[aChild] != aFather) {
            aChild = father[aChild];
            count++;
        }        

        count++;
        return count;
}

public int findFather(int x){
    if (father[x] == x){
        return x;
    }

    return findFather(father[x]);
}

public int findChild(int x){
    if (child[x] == x){
        return x;
    }

    return findChild(child[x]);
}

2nd solution

int[] father = null;
int[] size = null;

public ConnectingGraph2(int n) {
    size = new int[n + 1];
    father = new int[n + 1];

    for (int i = 0; i < n + 1; i++){
        size[i] = 1;
        father[i] = i;
    }
}

public void connect(int a, int b){
    int aFather = find(a);
    int bFather = find(b);

    if (aFather != bFather){
        father[aFather] = bFather;
        size[bFather] += size[aFather];
    }
}

public int query(int a){
    return size[find(a)];
}

public int find(int x){
    if (father[x] == x){
        return x;
    }

    return find(father[x]);
}