AcWing 1597. 社会集群-启发
原题链接
中等
作者:
CqAq
,
2024-03-14 21:18:06
,
所有人可见
,
阅读 29
算法1
(启发式合并方法)
时间复杂度$O(不知道…)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define QAQ "QAQ"
#define x first
#define y second
const int N = 1e4 + 11;
int n, p[N], sz[N];
unordered_map<int,int> root;
int find(int x){
while(p[x] ^ x) x = p[x];
return x;
//return p[x] == x ? x : p[x] = find(p[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return ;
if(sz[x] > sz[y]) swap(x,y);
p[x] = y;
sz[y] += sz[x];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= 1010; ++ i) p[i] = i, sz[i] = 1;
for(int i = 1; i <= n; ++ i){
int k; cin >> k;
char ch; cin >> ch;
int pre; cin >> pre;
for(int i = 1; i < k; ++ i){
int x; cin >> x;
merge(x, pre);
//p[find(x)] = find(pre);
}
root[i] = find(pre);///记录每一组输入的根
}
unordered_map<int,int> se;
vector<int> v;
for(const auto i : root) se[find(i.y)] ++;///记录根数(树的个数以及数上的节点数)
int sum = se.size();
cout << sum << '\n';
for(const auto i : se) v.push_back(i.y);
sort(v.begin(), v.end(), greater<int>());
cout << v[0];
for(int i = 1; i < v.size(); ++ i) cout << " " << v[i];
return 0;
}