Codeforces Round #170 (Div. 1) A. Learning Languages（连通块+dfs）

https://codeforces.com/contest/277/problem/A

题目大意：

有n个人，有m种语言；

这n个人分别会一些（也有可能会0种）；

问我们他们能否直接或者间接的交流？

如果不能的话，一个人去学习一门语言需要一块钱，我至少要准备多少钱才能够实现全部人的直接或间接交流？

input 
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
output 
0
input 
8 7
0
3 1 2 3
1 1
2 5 4
2 6 7
1 3
2 7 4
1 1
output 
2
input 
2 2
1 2
0
output 
1

数据范围都在100之内，特别小，所以我们直接暴力建边+dfs是没有问题的
但是需要格外注意一下特判全部同学的语言学习为0的时候

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
LL n,m,idx,t;//总共有n个人，m种语言
LL sum=0,res=0;
LL vis[N],a[M][M],f[M][M];//判断是否经过（联通）
void dfs(int x)
{
    vis[x]=1;
    for(int j=1;j<=n;j++)
    {
        //没跑过这个j点并且有一条路连接
        if(!vis[j]&&f[x][j])
            dfs(j);
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>idx;
            if(idx==0) sum++;//特判，一门语言都没学的话，那必须整一个
            while(idx--)
            {
                cin>>t;
                a[i][t]=1;//第i个人会第t种语言
            }
        }
        //联通
        for(int i=1;i<=n;i++)//一个人
        {
            for(int j=i+1;j<=n;j++)//和另一个人
            {
                for(int k=1;k<=m;k++)//判断语言
                {
                    if(a[i][k]&&a[j][k])//他会她也会
                    {
                        f[i][j]=1;//邻接矩阵
                        f[j][i]=1;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                res++;
                dfs(i);
            }
        }
        if(sum==n) cout<<n<<endl;
        else cout<<res-1<<endl;
    }
    return 0;
}