1 solutions
-
0
C++ :
#include<stdio.h> struct node{ int data; int rank; int parent; }; node t[1001]; int r[1000]; void set(node t[]){ int i; for(i=1;i<=1001;i++){ t[i].data=i; t[i].rank=0; t[i].parent=i; } } int find(node t[],int x){ if(x!=t[x].parent) return(find(t,t[x].parent)); else return x; } void un(node t[],int x,int y){ x=find(t,x); y=find(t,y); if(t[x].rank>t[y].rank){ t[y].parent=x; } else{ t[x].parent=y; if(t[x].rank==t[y].rank) t[y].rank++; } } int main(){ int m,a,b,N,mn=0,max=0; while(scanf("%d%d",&N,&m)!=EOF){ set(t); for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); un(t,a,b); } for(int i=1,bb=0;i<=N;i++){ if(t[i].parent==i){ r[bb]=i; bb++; max++; } } int z=0; for(int p=0;p<max;p++){ for(int i=1;i<=N;i++){ if(find(t,i)==r[p]) mn++; } if(mn>=z) z=mn; mn=0; } printf("%d\n",z); } return 0; }
- 1
Information
- ID
- 17340
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By