76 lines
1.6 KiB
C++
76 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
#pragma region 并查集模板
|
||
int p[101]; //存储元素的父节点
|
||
int Rank[101]; //存储树的高度(秩)
|
||
//建立并查集
|
||
void Build(int n) {
|
||
for (int i = 1; i <= n; ++i) {
|
||
p[i] = i; //父结点是元素自身
|
||
}
|
||
}
|
||
|
||
//查找根结点//路径压缩
|
||
int Find(int x) {
|
||
if (p[x] != x)
|
||
p[x] = Find(p[x]);
|
||
return p[x];
|
||
}
|
||
|
||
//按秩合并集合
|
||
void Union(int x, int y) {
|
||
x = Find(x);
|
||
y = Find(y);
|
||
if (Rank[x] < Rank[y]) p[x] = y;
|
||
else {
|
||
p[y] = x;
|
||
if (Rank[y] == Rank[x]) Rank[x]++;
|
||
}
|
||
}
|
||
|
||
#pragma endregion 并查集模板
|
||
|
||
bool comp(const pair<int, int> &a, const pair<int, int> &b) {
|
||
return a.second > b.second;
|
||
}
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1413.txt", "r", stdin);
|
||
|
||
int n, k;
|
||
cin >> n >> k;
|
||
|
||
//建立并查集
|
||
Build(n);
|
||
|
||
//合并集合
|
||
for (int i = 1; i <= k; ++i) {
|
||
int a, b;
|
||
cin >> a >> b;
|
||
Union(a, b);
|
||
}
|
||
|
||
//多少个家庭
|
||
unordered_map<int, int> _map;
|
||
for (int i = 1; i <= n; ++i) {
|
||
if (_map.count(p[i]) == 0) _map[p[i]] = 1;
|
||
else _map[p[i]]++;
|
||
}
|
||
cout << _map.size() << " ";
|
||
|
||
//迭代_map
|
||
//最大家庭人数(采用的技巧，unordered_map的value排序)
|
||
vector<pair<int, int> > b;
|
||
for (auto x:_map) {
|
||
b.push_back(x);
|
||
}
|
||
sort(b.begin(), b.end(), comp);
|
||
cout << b[0].second << endl;
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|