牛客 Interesting Computer Game

题目链接

题目大意：

给出了很多组数，每组数最多选一个，且不能选已经选过的数，求能选的数的最大个数

分析：

第一反应是贪心，但是发现贪心算法上面走不通。后来才知道是一道图论的题。还是题做少了啊。
在题中，如果把一组数字看成是一条边，那么问题就转化为了：图中对于每条边能够取一个相连顶点，求取的顶点的最大个数。
我们就可以对每个连通分量来考虑。如果连通分量是一棵树（e=v-1），那么每条边取一个顶点，该连通分量会有一个顶点无法取到。如果不是树，也就是说形成了环，那么无论是重边、自环还是圈，都可以证明可以将该连通分量的所有顶点取完。

做法：

由联通分量容易想到并查集，而我们还需要记录下连通分量是否形成环，就可以另开一个bool类型的数组f[MAX_N]来记录。其中f[i]表示以i为根节点的并查集是否成环。这样，每个连通分量是否成环就被存储在了该并查集的根节点中，合并时，就可以通过两个根节点各自是否成环来判断合并后的是否成环了。
同时，由于数据过大，需要进行离散化，可以采用map实现：给每个数字编号，直接处理编号即可。

AC代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int MAX_N=2e5+5;
int par[MAX_N];
bool f[MAX_N];//记录是否成环 
inline int read()
{
	int sum=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+c-48;c=getchar();}
	return sum*f;
}
map<int,int> mp;
int find(int x)
{
	return x==par[x]?x:par[x]=find(par[x]);
}
int main()
{
	int t=read(),ca=0;
	while(t--)
	{
		int tot=0;
		mp.clear();
		int n=read(),a,b;
		for(int i=0;i<n;i++)
		{
			a=read(),b=read();
			if(!mp.count(a))
			{
				mp[a]=++tot;//如果之前不存在就给数编号 
				par[tot]=tot,f[tot]=false;
			}
			if(!mp.count(b))
			{
				mp[b]=++tot;
				par[tot]=tot,f[tot]=false;
			}
			a=find(mp[a]),b=find(mp[b]);
			if(a==b)f[a]=true;
			else
			{
				par[a]=b;
				f[b]=f[b]||f[a];
			}
		}
		int ans=tot;
		for(int i=1;i<=tot;i++)if(par[i]==i&&!f[i])ans--;//没有成环才会有一个无法取的 
		cout<<"Case #"<<++ca<<": "<<ans<<endl;
	}
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45494989/article/details/107859115