1362：家庭问题(family)

 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 }