B - Learning Languages
思路
由于可以传译，所以可以将共同语言（包括传译）者视为一个集合（合并），最后查询总共集合数-1就是答案
注意
特判：有可能有公司所有人一种语言都不会，而答案不应为-1，所以需要特判
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 110;
const int M = 2e5+10;
int n,m;
bool g[N][N],cnt[N];
int p[N];
int find(int x){
if(p[x] != x)p[x] = find(p[x]);
return p[x];
}
void solve(){
bool f = 0;
cin >> n >> m; //n个人m种语言
for(int i = 1; i <= n; i ++ )p[i] = i;
for(int i = 1; i <= n; i ++ ){ //每个人会的语言
int num;
cin >> num;
if(num)f = 1;
while(num --){
int la;
cin >> la;
g[i][la] = 1;
}
}
for(int j = 1; j <= m; j ++ ){ //每种语言
vector<int> v;
for(int i = 1; i <= n; i ++ ){ //选取会的人
if(g[i][j])v.push_back(i);
}
for(int i = 1; i < v.size(); i ++ ){
p[find(v[i])] = find(v[0]); //合并
}
}
for(int i = 1; i <= n; i ++){
cnt[find(i)] = 1;
}
int ans = 0;
for(int i = 1; i <= n; i ++){
if(cnt[i])ans ++;
}
if(f)cout << ans - 1 << nl;
else cout << n << nl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}