Codeforces Round 170 (Div. 1)A. Learning Languages并查集

本文主要是介绍Codeforces Round 170 (Div. 1)A. Learning Languages并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果两个人会的语言中有共同语言那么他们之间就可以交流，并且如果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;
}

这篇关于Codeforces Round 170 (Div. 1)A. Learning Languages并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---