L2-2 社交集群 （25 分)（一个写挫的并查集）

题目：

思路：

就是一个并查集的裸题，不过在数据查找方面可能不好处理，暴力完全可以解决这个问题啊！！

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iomanip>
#define MOD 998244353
#define MAX 1000000000
#define inf 0x3f3f3f3f3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)

using namespace std;
typedef long long ll;
const int maxn = 2010;
int fa[maxn],vis[maxn];

void init()
{
    for(int i=0; i<maxn; i++)
    {
        fa[i] = i;
        vis[i] = 1;
    }
}

int _find(int x)
{
    return fa[x]==x ? x : fa[x] = _find(fa[x]);
}

void _union(int x,int y)
{
    int tx = _find(x);
    int ty = _find(y);
    if(tx!=ty)
    {
        fa[ty] = tx;
        vis[tx] += vis[ty];//更新这个社交集群中的人数
    }
    return;
}

int main()
{
    init();
    vector<set<int> > vc;
    int n,k,x;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        set<int> st;
        scanf("%d:" ,&k);
        for(int j=0; j<k; j++)
        {
            scanf("%d",&x);
            st.insert(x);
            for(int p=0; p<i; p++)//暴力查找有共同兴趣的人
            {
                if(vc[p].count(x))//进行合并
                {
                    _union(i,p);
                    break;
                }
            }
        }
        vc.push_back(st);
    }
    vector<int> ans;
    for(int i=0; i<n; i++)
    {
        if(fa[i] == i)
        {
            ans.push_back(vis[i]);
        }
    }
    sort(ans.begin(),ans.end(),greater<int>() );
    printf("%d
",ans.size());
    for(int i=0; i<ans.size(); i++)
    {
        if(i) printf(" ");
        printf("%d",ans[i]);
    }
    return 0;
}
/*
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
*/
/*
3
4 3 1
*/