Untitled

 avatar
unknown
plain_text
5 years ago
1.9 kB
6
Indexable
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
class TestClass {
    
    public static void main(String args[] ) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr1= br.readLine().split(" ");
        int n= Integer.parseInt(strArr1[0]);
        int m= Integer.parseInt(strArr1[1]);
        
        int[] parent= new int[n+1];
        int[] size= new int[n+1];
        
        for(int i=0;i<=n;i++){
            parent[i]=i;
            size[i]=1;
        }
        
        while(m-->0){
            String[] strArr= br.readLine().split(" ");
            int x= Integer.parseInt(strArr[0]);
            int y= Integer.parseInt(strArr[1]);
            
            union(parent,size,x,y);
            printSizeAllConnectedComponents(parent,size);
        }
        
        
    }
    
    static int find(int[] parent, int a){
        if(parent[a]==a){
            return a;
        }
        
        return find(parent,parent[a]);
    }
    
    static void union(int[] parent, int[] size, int a, int b){
        int root_a= find(parent,a);
        int root_b= find(parent,b);
        if(root_a==root_b){
            return;
        }
        if(size[root_a]<size[root_b]){
            parent[root_a]=root_b;
            size[root_b]+=size[root_a];
        }else{
            parent[root_b]=root_a;
            size[root_a]+=size[root_b];
        }
    }
    
    static void printSizeAllConnectedComponents(int[] parent, int[] size){
        List<Integer> list= new ArrayList<>();
        
        for(int i=1;i<size.length;i++){
            if(parent[i]==i){
                list.add(size[i]);
            }
        }
        Collections.sort(list);
        for(Integer s:list){
            System.out.print(s+" ");
        }
        System.out.println(" ");
    }
}
Editor is loading...