题目连接:请戳这里。
题目大意及思路:就是找学生最多的那个集合。注意一点的是“or there is only one boy left.”
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #define N 10000000+10 using namespace std; int f[N],num[N]; void Init(int n) { for(int i=1;i<=n;i++) { f[i]=i; num[i]=1; } } int Find(int x) { return f[x]==x?x:f[x]=Find(f[x]); } void Merge(int a,int b) { int ra=Find(a),rb=Find(b); if(ra==rb) return ; else { f[rb]=ra; num[ra]+=num[rb]; } } int main() { int m; while(scanf("%d",&m)==1) { Init(N); int n=0; for(int i=0;i<m;i++) { int a,b; scanf("%d %d",&a,&b); n=max(n,max(a,b)); Merge(a,b); } int Max=1; //当n=0时,答案应该是1~ for(int i=1;i<=n;i++) Max=max(Max,num[i]); printf("%d\n",Max); } return 0; }
原文:http://blog.csdn.net/darwin_/article/details/42803709