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), add an edge to connect nodeaand node b.

2.query(a, b)`, check if two nodes are connected

Example

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

    UnionFind uf;
    public ConnectingGraph(int n) {
        this.uf = new UnionFind(n);
    }

    public void connect(int a, int b) {
        uf.union(a, b);
    }

    public boolean  query(int a, int b) {
        return uf.compressed_find(a) == uf.compressed_find(b);
    }
    class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

            public UnionFind(int m){
                for(int i = 1; i <= m; i++){
                    father.put(i, i);
                }
            }

            public int compressed_find(int x){
                int parent = x;
                while(parent != father.get(parent)){
                    parent = father.get(parent);
                }
                int next;
                while(x != father.get(x)){
                    next = father.get(x);
                    father.put(x, parent);
                    x = next;
                }
                return parent;
            }

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                }
            }
    }

Follow up 1:

query(a), Returns the number of connected component nodes which include nodea

Solution: 多用一个hashmap存count, union时，count.put(fa_y, count.get(fa_y) + count.get(fa_x));

    UnionFind uf;

    public ConnectingGraph2(int n) {
        this.uf = new UnionFind(n);
    }

    public void connect(int a, int b) {
        uf.union(a, b);
    }

    public int query(int a) {
        int root = uf.compressed_find(a);
        if(!uf.count.containsKey(root)){
            return 0;
        }
        return uf.count.get(root);
    }
    class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();

            public UnionFind(int m){
                for(int i = 1; i <= m; i++){
                    father.put(i, i);
                    count.put(i, 1);
                }
            }

            public int compressed_find(int x){
                int parent = x;
                while(parent != father.get(parent)){
                    parent = father.get(parent);
                }
                int next;
                while(x != father.get(x)){
                    next = father.get(x);
                    father.put(x, parent);
                    x = next;
                }
                return parent;
            }

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                    count.put(fa_y, count.get(fa_y) + count.get(fa_x));
                    // count.put(fa_y, count.get(fa_y) + 1);
                }
            }
    }

Follow 2:

query(), Returns the number of connected component in the graph

    UnionFind uf;
    int n;
    public ConnectingGraph3(int n) {
        this.uf = new UnionFind(n);
        this.n = n;
    }

    public void connect(int a, int b) {
        uf.union(a, b);
    }

    public int query() {
        return n;
    }
     class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

            public UnionFind(int m){
                for(int i = 1; i <= m; i++){
                    father.put(i, i);
                }
            }

            public int compressed_find(int x){
                int parent = x;
                while(parent != father.get(parent)){
                    parent = father.get(parent);
                }
                int next;
                while(x != father.get(x)){
                    next = father.get(x);
                    father.put(x, parent);
                    x = next;
                }
                return parent;
            }

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                    n--;
                }
            }
    }