【题目描述】

有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关.系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。

当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？

例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)

此时，6个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为一个家庭，第一个家庭的人数为最多。

【输入】

第一行为n,k二个整数（1≤n≤100）（用空格分隔）;

接下来的k行，每行二个整数（用空格分隔）表示关系。

【输出】

二个整数（分别表示家庭个数和最大家庭人数）。

【输入样例】

6  3 1  2 1  3 4  5

【输出样例】

3 3

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 301 #define MOD 123 #define E 1e-6 using namespace std; int father[N]; int a[N]; int Find(int x) { if(father[x]==x) return x; return father[x]=Find(father[x]); } void Union(int x,int y) { int f1=Find(x); int f2=Find(y); if(f1!=f2) father[f2]=f1; } int main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=k;i++) { int x,y; cin>>x>>y; Union(x,y); } for(int i=1;i<=n;i++) a[Find(i)]++; int cnt_1=0,cnt_2=0; for(int i=1;i<=n;i++) if(a[i]>cnt_2) cnt_2=a[i]; for(int i=1;i<=n;i++) if(father[i]==i) cnt_1++; cout<<cnt_1<<" "<<cnt_2<<endl; return 0; }