【题解】家庭问题
【题目描述】
有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行，每行二个整数（用空格分隔）表示关系。
【输出描述】
二个整数（分别表示家庭个数和最大家庭人数）。
【样例输入】
6 3 1 2 1 3 4 5
【样例输出】
3 3
【题目分析】
并查集思路
【参考答案】
#include <bits/stdc++.h>
using namespace std;
int f[105];
int a[105];//结点下的孩子数量
int n, k, cnt, mx;
void init() {
//由于从1编号的，所以for就不从0了
for (int i = 1; i <= n; ++i) {
f[i] = i;
}
}
int find(int x) {
if (f[x] == x)
return x;
//递归返回时，不断将根节点作为每一个结点的父亲
return f[x] = find(f[x]);
}
//合并两个结点
void merge(int a, int b) {
a = find(a);
b = find(b);
f[a] = b;
}
int main() {
cin.tie(0);
cin >> n >> k;
init();
for (int i = 0; i < k; ++i) {
int x, y;
cin >> x >> y;
merge(x, y);
}
for (int i = 1; i <= n; ++i) {
a[find(i)]++;
if (f[i] == i) {
//这是查根节点的数目，可以说明有几个家庭数
cnt++;
}
}
for (int i = 1; i <= n; ++i) {
mx = max(mx, a[i]);
}
cout << cnt << " " << mx;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。