Untitled
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...