1 solutions

  • 0
    @ 2025-11-5 15:55:49

    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