【题解-信息学奥赛一本通】1362：家庭问题(family)
)
题目：1362：家庭问题(family)
题目描述
有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行，每行二个整数（用空格分隔）表示关系。
输出
二个整数（分别表示家庭个数和最大家庭人数）。
时空限制
1s / 64MB
样例输入
6 3 1 2 1 3 4 5样例输出
3 3代码
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=20000+10;intn,k,x,y,ans;vector<int>a;PII g[N];boolvis[N];voidsplitnum(intnum){a.clear();while(num>0){a.push_back(num%10);num/=10;}reverse(a.begin(),a.end());}inttrans(intt,inty){intsum=0;for(inti=0;i<a.size();i++){if(i!=t)sum=sum*10+a[i];elsesum=sum*10+y;}returnsum;}voidbfs(intm){queue<int>q;q.push(m);vis[m]=true;ans=1;while(!q.empty()){intt=q.front();q.pop();splitnum(t);for(inti=0;i<a.size();i++)for(intj=0;j<k;j++)if(a[i]==g[j].first){inttt=trans(i,g[j].second);if(!vis[tt]){q.push(tt);vis[tt]=true;ans++;}}}}intmain(){cin>>n>>k;for(inti=0;i<k;i++){cin>>x>>y;g[i].first=x,g[i].second=y;}bfs(n);cout<<ans;return0;}