如果两个人会的语言中有共同语言那么他们之间就可以交流,并且如果a和b可以交流,b和c可以交流,那么a和c也可以交流,具有传递性,就容易联想到并查集,我们将人和语言看成元素,一个人会几种语言的话,就将这些语言和这个人所在的集合合并,最后求一下人一共在几个连通块中,连通块的个数-1就是答案,有一种比较坑的情况是所有人都不会语言,那么每个人都需要学一种语言,人数就是答案。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
const int N=1010;
int fa[N],n,m,vis[N];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int px=find(x),py=find(y);
if(px!=py) fa[py]=px;
}
void solve()
{
cin>>n>>m;
rep(i,1,n+m) fa[i]=i;
bool st=false;
rep(i,1,n)
{
int k;cin>>k;
if(k) st=true;
rep(j,1,k)
{
int x;cin>>x;
merge(i,x+n);
}
}
int cnt=0;
rep(i,1,n) if(find(i)==i) cnt++;
if(st) cout<<cnt-1<<endl;
else cout<<cnt<<endl;
}
int main()
{
IOS
// freopen("1.in", "r", stdin);
int t;
// cin>>t;
// while(t--)
solve();
return 0;
}
标签:语言,int,rep,查集,Codeforces,long,st,Languages,define
From: https://www.cnblogs.com/cxy8/p/17985895