Split Into Two Sets Codeforces 1702E

Problem - 1702E - Codeforces

题目大意：每张多米诺骨牌上有1到n之间的两个数字，现给出n张牌，问能不能把骨牌分成两副，使得每一副骨牌中没有重复的数字。

思路：很明显是个二分图检验问题，但每张骨牌上两个数字需要单独考虑，所以不能以骨牌为点建图，那么我们拿（5,6）（5,7）（8,6）（7,8）这四张牌举例，可以发现（5,6）（5,7）不能在一副牌中，（8,6）（7,8）不能是一副，即有相同数字的两张骨牌不能是一副。首先每个数字一定出现了两次，且我们只需要将出现的两个地方中的一个染成白色，同一个数字出现的另一张骨牌上的另一个数字就得被染成黑色比如我们可以把（5,6）中的5染成白色，那么（5,7）中的7就得是黑色，接着（7,8）中的8是白色（8,6）中的6是黑色，这样我们就得到了（5,6）（7,8）和（5,7）（8,6）两副牌，所以我们只需将每张骨牌上的两个数字之间连边，然后用染色法进行二分图检验

#include
using namespace std;
const int N = 2e5 + 5;
vector<int>g[N];
int n;
int col[N], cnt[N];
bool flag = 1;
void dfs(int now)//记录当前的点的编号
{
	if (!flag)
		return;
	for (int i = 0; i < g[now].size(); i++)
	{//遍历当前点连接的所有边
		int next = g[now][i];		
		if (!col[next])
		{
			col[next] = 3 - col[now];
			dfs(next);//如果下一个点没有被涂过色，就涂不同的颜色，继续向下遍历
		}			
		else if (col[next] == col[now])
		{//如果当前点和下一个点颜色相同，则不符合二分图规则
			flag = 0;
			return;
		}
	}
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			g[i].clear();
			col[i] = cnt[i] = 0;//初始化
		}
		flag = 1;//判断是否是二分图的标志
		for (int i = 1; i <= n; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			cnt[u]++;
			cnt[v]++;//记录每个数字出现的次数
			if (cnt[u] > 2 || cnt[v] > 2)
				flag = 0;//如果出现次数多于2，则无法平分
			g[u].push_back(v);
			g[v].push_back(u);//邻接表存图
		}		
		for (int i = 1; i <= n; i++)
		{//遍历所有连通分量
			if (col[i] == 0 && flag)
			{
				col[i] = 1;//初始化每个连通分量的第一个点的颜色
				dfs(i);
			}				
		}
		if (flag)
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}