http://ybt.ssoier.cn:8088/problem_show.php?pid=1362
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n, k;//按要求输入 4 int a, b;//按要求输入 5 int rel[105][105];//用于存储各个成员之间的关系 6 int vis[105];//记录是否被访问过 7 int que[10010];//定义队列 8 int f, r;//定义队首队尾 9 int fm_cnt, fm_num, fm_max;//存放答案 fm_num用于记录每个家庭成员个数 10 void pr() {//用于测试 11 for(int i=1; i<=n; i++) { 12 cout<<i<<"-"<<vis[i]<<","; 13 } 14 } 15 int main() { 16 cin>>n>>k; 17 while(k--) { 18 cin>>a>>b; 19 rel[a][b]=rel[b][a]=1;//关系是相互队 20 rel[a][a]=rel[b][b]=1;//自己与自己建立关系 21 } 22 for(int i=1; i<=n; i++) { 23 if(vis[i]==0) {//以未被访问队成员进行搜索 24 fm_cnt++;//每个未被访问队成员代表一个独立队家庭 25 f=r=1;//初始化队列 26 que[r]=i;//入队 27 vis[i]=1;//更改访问状态 28 int fcnt=1;//初始化家庭成员个数 29 while(f<=r) { 30 int fq=que[f];//获得队首信息 31 for(int j=1; j<=n; j++) {//遍历与每个成员是否存在关系 32 if((rel[fq][j]==1 || rel[j][fq]==1 ) && vis[j]==0) {//确定关系是否合法且未被访问 33 fcnt++;//增加家庭成员数量 34 vis[j]=1;//更改访问状态 35 r++;//队尾后移准备入队 36 que[r]=j;//家庭成员入队 37 } 38 } 39 f++;//队首出队 40 } 41 fm_max=max(fcnt, fm_max);//更新最大值 42 } 43 } 44 cout<<fm_cnt<<" "<<fm_max; 45 46 return 0; 47 }