【题解】家庭问题
【题目描述】
有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; }