CF1209D Cow and Snacks (思维+并查集)

「luogu题目传送门」 CF1209D Cow and Snacks

题意：

一个商店有n中零食，m个客人，每个客人有两个喜欢的零食x_i,y_i,如果有喜欢的零食，每个客人会全部买走，如何安排顺序才能使一个零食也买不到的客人最少？

题解

我们不论如何，第一个人一定是会选走两个的，那么我们要尽量使以后的每一个人与前一个人有一个重合，这样他就只会买走一个了。
我们能用一个零食来换一个人的名额，应该是最优的，如何安排呢？
我们将零食看做点，如果一个人同时喜欢两个零食，就将这两个零食连一条边，这样对于整个图中的一个大小为size的联通块，我们可以知道，它可以增加size-1个高兴的名额，对于每一个联通块都如此处理，用总人数-高兴的人数 就得到了不高兴的

代码

#include <cstdio>
const int maxn=2e5+5;
int fa[maxn],siz[maxn],ans;
int n,m;
int Find_root(int x){
	return fa[x]==x?x:fa[x]=Find_root(fa[x]);
}
int main(){
//	freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1;
	for(int i=1,x,y,rx,ry;i<=m;++i){
		scanf("%d%d",&x,&y);
		rx=Find_root(x);
		ry=Find_root(y);
		if(rx!=ry){
			fa[rx]=ry;
			siz[ry]+=siz[rx];
		}
	}
	for(int i=1;i<=n;++i){
		if(fa[i]==i) ans+=(siz[i]-1);
	}
	printf("%d
",m-ans);
	return 0;
}