题目描述

一直不知道acwing这个input console怎么用

样例

class UnionFind{
    private int size; // the total number of elements in this union 
    private int[] sz; //Use to track the sizes of each of the components
    private int numComponents; //tracks the number of components in the uinon
    private int[] id; //id[i] points to the parent of i, if id[i] = i, then i is a root node

    public void UnionFind(int size){
        this.size = numComponents = size;
        sz = new int[size];
        id = new int[size];

        for(int i = 0; i < size; i++){
            id[i] = i; //Initially every one is itself root
            sz[i] = 1;  //each component is originlally of size one
        }
    }

    public int find(int p){
        //Find the root of the compinent/set
        int root = p;
        while(root != id[root]){
            root = id[root];
        }
        //Path Compression
        while(p != root){
            int next = id[p];
            id[p] = root;
            p = next;
        }
        return root;
    }

    public void union(int p, int q){
        int root1 = find(p);
        int root2 = find(q);
        //These elements are already in the same group
        if(root1 == root2) return;
        //Merge 2 compinents
        //Merge the smaller one into the larger one
        if(sz[root1] < sz[root2]){
            sz[root2] += sz[root1];
            id[root1] = root2;
        }else{
            sz[root1] += sz[root2];
            id[root2] = root1;
        }
        numComponents--;
    }

    public boolean connected(int p, int q){
        return find(p) == find(q);
    }

    public int componentSize(int p){
        return sz[find(p)];
    }

    public int size(){
        return size;
    }

    public int components(){
        return numComponents;
    }

}