Connecting Graph

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:

Use union find to do connect(union), while doing union, add count of connection at representative node. When query, do find(x) first, and count of representative node is the number connections.

Answer:

public class ConnectingGraph2 {

    private int[] father = null;
    private int[] count = null;

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

    private int find(int x)
    {
        if(father[x] == x)
        {
            return x;
        }
        return father[x] = find(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[rootB] += count[rootA];
        }
    }

    public int query(int a) {
        // Write your code here
        return count[find(a)];
    }
}