信息学奥赛一本通数据结构 1362：家庭问题(family) 第二章队列

长春高老师编程

413人浏览 · 2024-03-21 15:28:21

长春高老师编程 · 2024-03-21 15:28:21 发布

1362：家庭问题(family)

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

有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行，每行二个整数（用空格分隔）表示关系。

【输出】

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

【输入样例】

【输出样例】

3 3

解析：枚举所有人，对于没有加入家庭的人进行广度优先搜索，搜索其所有家庭成员并标记。

详见代码：

#include <bits/stdc++.h>
using namespace std;
int n,k;
int f[105];//f[i]标记编号为i的人是否已经是家庭成员了
int ans=0;
int sum=0;
vector<int> s[105];//s[i]表示第i个人和那些人有关系
queue<int> q;
void bfs(int x) {
    int su=0;//家庭人数
    q.push(x);//第一个人入队
    f[x]=1;//标记
    su++;
    while (q.size()) {//只要队列非空
        int t=q.front();//取队首人id
        q.pop();//弹出队首
        for (int i=0;i<s[t].size();i++) {//枚举队首人的所有关系
            if (f[s[t][i]]==0) {//如果没有标记
                q.push(s[t][i]);//入队
                f[s[t][i]]=1;//标记
                su++;//家庭人数加一
            }
        }
    }
    sum=max(sum,su);//取最大家庭人数
    return ;
}
int main() {
    cin >>n>>k;
    for (int i=1;i<=k;i++) {
        int a,b;
        cin >>a>>b;
        s[a].push_back(b);
        s[b].push_back(a);
    }
    for (int i=1;i<=n;i++) {//枚举每个人
        if (f[i]==0) {//未加入家庭的
            bfs(i);//广搜这个家庭的所有成员并标记
            ans++;//多一个家庭
        }
    }
    cout <<ans<<' '<<sum<<endl;
    return 0;
}