AcWing 1597. 有相同爱好只需要合并一次
原题链接
中等
作者:
fei0825
,
2023-05-28 15:55:38
,
所有人可见
,
阅读 189
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int p[N], sz[N], cnt, res[N], idx;
int hb[N];
bool st[N];
int find(int x){
if( p[x]!=x ) p[x]=find(p[x]);
return p[x];
}
void merge(int a, int b){
a=find(a), b=find(b);
if( a!=b ){
p[a] = b;
sz[b] += sz[a];
cnt--;
}
}
int main(){
for( int i=1; i<N; i++ ) p[i]=i, sz[i]=1;
int n;
scanf("%d", &n);
cnt = n;
for( int i=1; i<=n; i++ ){
int k, x;
scanf("%d: ", &k);
for( int j=0; j<k; j++ ){
scanf("%d", &x);
if( hb[x]!=0 ) merge(i, hb[x]);
hb[x] = i;
}
}
printf("%d\n", cnt);
for( int i=1; i<=n; i++ ){
int t = find(i);
if( !st[t] ){
st[t] = true;
res[idx++] = sz[t];
}
}
sort(res, res+idx, greater<int>());
for( int i=0; i<idx; i++ ){
if( i ) printf(" ");
printf("%d", res[i]);
}
puts("");
return 0;
}