题目:求最大的集合的元素个数。
分析:并查集。
注意:输入使用while( scanf("%d",&T) != EOF )会TLE。
#include <stdio.h> #include <stdlib.h> //union_set_begin int sets[ 30001 ]; int rank[ 30001 ]; int size[ 30001 ]; void union_set( int n ) { for ( int i = 0 ; i <= n ; ++ i ) { rank[i] = 0; size[i] = 1; sets[i] = i; } } int Find( int a ) { if ( a != sets[a] ) sets[a] = Find( sets[a] ); return sets[a]; } int Union( int a, int b ) { if ( rank[a] > rank[b] ) { sets[b] = a; size[a] += size[b]; }else { sets[a] = b; size[b] += size[a]; if ( rank[a] == rank[b] ) rank[b] ++; } } //union_set_end int x[500001]; int y[500001]; int main() { int T,N,M,a,b; scanf("%d",&T); while ( T -- ) { scanf("%d%d",&N,&M); union_set( N ); for ( int i = 1 ; i <= M ; ++ i ) scanf("%d%d",&x[i],&y[i]); for ( int i = 1 ; i <= M ; ++ i ) { a = Find( x[i] ); b = Find( y[i] ); if ( a != b ) Union( a, b ); } int max = 1; for ( int i = 1 ; i <= N ; ++ i ) if ( max < size[i] ) max = size[i]; printf("%d\n",max); } return 0; }