首页 > 其他分享 >Codeforces Round 170 (Div. 1)A. Learning Languages并查集

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

时间:2024-01-24 21:34:40浏览次数:32  
标签:语言 int rep 查集 Codeforces long st Languages define

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

相关文章

  • P1536 村村通(并查集)
    村村通题目描述某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府"村村通工程"的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路?输入格式输入包含若干......
  • CF-1184-E3-最小生成树+倍增+并查集
    1184-E3题目大意给定一个\(n\)个点,\(m\)条边的无向图,边带权。对于每条边,你需要找到最大值\(x\),使得把这条边的权值修改为\(x\)后能够出现在最小生成树上。Solution先把整个图的最小生成树弄出来,然后将边分为树边以及非树边来考虑:非树边:对于一个非树边连接了\(x\)和\(y\)的......
  • CodeForces 1010F Tree
    洛谷传送门CF传送门educational的。另一道类似的题是[ABC269Ex]Antichain(但是我还没写)。考虑令\(b_u=a_u-\sum\limits_{v\inson_u}a_v\)。那么\(\sum\limits_{i=1}^nb_i=a_1=x\),且\(\foralli\in[1,n],b_i\ge0\)。所以最后连通块内有\(y\)个点,那......
  • 并查集与反集——P1892团伙
    并查集并查集如其名,合并与查找查找intfind(intkey){ if(fa[key]==key)returnkey; elsereturnfa[key]=find(fa[key]);}合并voidunite(intx,inty){ intfax=find(x); intfay=find(y); fa[fax]=fay; return;}反集处理并查集合并问题的敌对/......
  • hey_left 14 Codeforces Round 849 (Div. 4) 续
    题目链接F.区间修改,单点查询,考虑用树状数组可以维护每个点需要操作的次数然后直接对询问的点进行操作#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;#defineintlonglongstructTreeArray{vector<int>tree;TreeArray(intn){......
  • 并查集
    并查集是一种集合结构,用来处理集合的合并和查询问题。主要有两个函数:合并和查询合并函数表示合并两个不同的集合查询表示当前元素属于那个集合逻辑结构是单链表的结构,每个节点向上指向一个属于的集合的代表元素,这个集合的代表元素的next指向它自己成环,表示这个集合的代表元素......
  • hey_left 13 Codeforces Round 849 (Div. 4)
    题目链接A.可用map标记这几个字符,判在不在即可#include<bits/stdc++.h>usingnamespacestd;strings="codeforces";map<char,bool>mp;voidsolve(){charc;cin>>c;if(mp[c]){cout<<"YES"<<'\n';......
  • CF-292-D-并查集
    292-D题目大意给定一张无向图,由\(n\)个顶点\(m\)条边。有\(q\)次询问,每次询问将\([l,r]\)的边删去,问图中有多少连通分量。Solution涉及连通分量,尝试应用并查集解决。记录一个前缀并查集\(pre[i]\),表示前\(i\)条边连通后的图;和一个后缀并查集\(suf[i]\),表示后\(m-i\)条边连通......
  • CodeForces 1609G A Stroll Around the Matrix
    洛谷传送门CF传送门我独立做出一道*3000?考虑对于单次询问,除了\(O(nm)\)的dp,有没有什么方法能快速算出答案。发现若\(a_{i+1}-a_i<b_{j+1}-b_j\)则\(i\getsi+1\),否则\(j\getsj+1\)是最优的。这个贪心的证明不难,考虑当前新走到某一行或某一列的贡献......
  • CodeForces 1609F Interesting Sections
    洛谷传送门CF传送门看到\(\max,\min\)考虑单调栈。枚举右端点,计算有多少个符合条件的左端点。单调栈维护的是对于每个右端点,以每个点为左端点的后缀\(\max,\min\)形成的极长的段。先枚举\(\text{popcount}=k\),然后如果一个段的\(\max\)的\(\text{popcount}=k\)......