【题解-信息学奥赛一本通】1362：家庭问题(family)

题目1362家庭问题(family)题目描述有n个人编号为1,2,……n另外还知道存在K个关系。一个关系的表达为二元组αβ形式表示αβ为同一家庭的成员。当nk和k个关系给出之后求出其中共有多少个家庭、最大的家庭中有多少人例如n6k3三个关系为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代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN2000010;intn,k,x,y,ans;vectorinta;PII g[N];boolvis[N];voidsplitnum(intnum){a.clear();while(num0){a.push_back(num%10);num/10;}reverse(a.begin(),a.end());}inttrans(intt,inty){intsum0;for(inti0;ia.size();i){if(i!t)sumsum*10a[i];elsesumsum*10y;}returnsum;}voidbfs(intm){queueintq;q.push(m);vis[m]true;ans1;while(!q.empty()){inttq.front();q.pop();splitnum(t);for(inti0;ia.size();i)for(intj0;jk;j)if(a[i]g[j].first){inttttrans(i,g[j].second);if(!vis[tt]){q.push(tt);vis[tt]true;ans;}}}}intmain(){cinnk;for(inti0;ik;i){cinxy;g[i].firstx,g[i].secondy;}bfs(n);coutans;return0;}结果