考虑用并查集维护

为什么是这样呢,题意说的很清楚,相当于是给很多块连边,求最少的数量。那我们就把会同一种语言的放进一个大块中,最后得到 $tot$ 个块就需要 $tot-1$ 条边了

我们具体来分析一下合并的问题。首先没有必要存 $n$ 个人的信息,我们最多只需要 $m$ 个代表,说明有多少不同的语言是必须学的。假设 $n$ 个人每个人会的都不同,那就必须有 $n-1$ 个语言得学。每进来一个人,只要会之前存在过的语言就并到那个语言集中,每成功合并一次就 $ans--$

另外还有一个大坑就是如果 $n$ 个人没一个会说话就得学 $n$ 个语言

代码:

#include <bits/stdc++.h>
using namespace std;

#define N 103
int n, res;
int vis[N];
//vis[i]记录着会第i种语言的人的编号(1<=i<=n)
//也是指上文中的“代表”

bool NA;
//记录特殊情况(是否需要学n种语言)

struct unionFindSet
{
    int fa[N];
    inline void clear()
    {
        for(int i=1; i<=n; ++i) fa[i]=i;
        return ;
    }

    int find(int x)
    {
        if(fa[x] == x) return x;
        return fa[x]=find(fa[x]);
    }

    inline void unite(int x, int y)
    {
        int fx=find(x), fy=find(y);
        if(fx != fy) fa[fx]=fy, --res;
        //注意必须是成功合并一次才ans--
        return ;
    }
} T;

int main(void)
{
    scanf("%d%*d", &n);
    T.clear(); res=n-1;
    //把ans赋初值,就是最多需要的语言数
    for(int i=1; i<=n; ++i)
    {
        int cnt, x; scanf("%d", &cnt);
        if(cnt && !NA) NA=true;
        //如果有一个人会说话,就不需要n种语言
        while(cnt--)
        {
            scanf("%d", &x);
            if(vis[x]) T.unite(vis[x], i);
            else vis[x]=i;
        }
    }
    printf("%d", NA ? res : n);
    //最后判断一下就好了
    return 0;
}