E. Split Into Two Sets(染色法判断二分图)

Problem - 1702E - Codeforces

波利卡普最近得到了一组n（数字n-偶数）的骨牌。每块多米诺骨牌包含1到n的两个整数。

他能把所有的骨牌分成两组，使每组骨牌上的数字都不一样吗？每张多米诺骨牌必须正好进入两组中的一组。

例如，如果他有4张多米诺骨牌：{1,4}、{1,3}、{3,2}和{4,2}，那么波利卡普就能按要求把它们分成两组。第一组可以包括第一张和第三张骨牌（{1,4}和{3,2}），第二组是第二张和第四张（{1,3}和{4,2}）。

输入
第一行包含一个整数t（1≤t≤104）--测试案例的数量。

接下来是测试用例的描述。

每个测试用例的第一行包含一个偶数整数n（2≤n≤2⋅105）--多米诺骨牌的数量。

接下来的n行包含一对数字ai和bi（1≤ai,bi≤n），描述第i块多米诺骨牌上的数字。

保证所有测试案例的n之和不超过2⋅105。

输出
对每个测试案例打印。

如果有可能将n块多米诺骨牌分成两组，使每组多米诺骨牌上的数字不同，则为YES。
如果不可能，则打印NO。
你可以在任何情况下打印YES和NO（例如，字符串yEs、yes、Yes和YES将被识别为一个肯定的答案）。

例子
inputCopy
6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
输出拷贝
是
拒绝
不
是
是
无
备注
在第一个测试案例中，多米诺骨牌可以被划分如下。

第一组骨牌：[{1,2},{4,3}] 。
第二组骨牌：[{2,1},{3,4}] 。
换句话说，在第一组中，我们采取数字为1和2的骨牌，在第二组中，我们采取数字为3和4的骨牌。
在第二个测试案例中，没有办法将多米诺骨牌分成两组，其中至少有一组会包含重复的数字。

题解:
根据例子我们发现

将每一个骨牌看做双向边连接, 如样例5

2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
连完后建成的图为 {1,2}-{2,1}, {3,4}-{3,4}, {5,6}-{6,8}-{8,7}-{7,5}三个环 不难发现当环是偶数环时候, 我们可以隔着取放在一个集合里面, 如 {5,6}-{6,8}-{8,7}-{7,5}, 取{5,6},{8,7}放在一个集合, 其他两个放在另一个集合(即构建出一个二分图), 这样取两个集合中是不会出现重复的, 而若出现奇数环时, 取牌必定会有重复, 所以建完图后, 判断是否存在奇数环即可.

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
//1 1 3 3 3
vector<int> p[200050];
int n;
map<int,int> vis;
map<int,int> st;
int dfs(int u,int x)
{
	st[u] = x;
	for(int i = 0;i < p[u].size();i++)
	{
		int j = p[u][i];
		if(!st[j])
		{
			if(!dfs(j,3-x))
			{
				return 0;
			}
		}
		else if(st[j] == x)
		{
			return 0;
		}
	}
	return 1;
}
void solve()
{
	cin >> n;
	vis.clear();
	st.clear();
	for(int i = 1;i <= n;i++)
	{
		p[i].clear();
	}
	int f = 0;
	for(int i = 1;i <= n;i++)
	{
		int a,b;
		cin >> a >> b;
		if(a == b)
		{
			f = 1;
		}
		vis[a]++,vis[b]++;
		if(vis[a]>2||vis[b] > 2)
		{
			f = 1;
		}
		p[a].push_back(b);
		p[b].push_back(a);
	}
		if(f)
		{
			cout<<"NO\n";
			return ;
		}
	for(int i = 1;i <= n;i++)
	{
		if(!st[i])
		{
			if(!dfs(i,1))
			{
				cout<<"NO\n";
				return ;
			}
		}
	}
 
	cout<<"YES\n";
 
	
}
signed main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//2 5
//3
//9 7 
 
 
//2  3 4 3