CF1702E 题解

wonderfish / 2023-08-02 / 原文

题意

$t$组数据（$1 \le t \le 10^{4} $），每组数据给一个偶数 $n$（$2 \le n \le 2 \cdot 10^{5}$），有 $n$ 个多米诺骨牌，每块多米诺骨牌包含两个整数 $a_{i}$ 和 $b_{i}$ （$1 \le a_{i},b_{i} \le n$），要求把这 $n$ 块多米诺骨牌分入两个集合使得每个集合中的数互不相同，每个多米诺骨牌都必须被分入一个集合。

解题思路

由题意得每个集合中有 $n$ 个数，每个数互不相同且都在 $1$ 和 $n$ 之间，所以 $1$ 到 $n$ 之间的每个数都会在每个集合中出现且只出现一次，因此总共的 $2 \cdot n$ 个数中，$1$ 到 $n$ 都出现两次，所以如果有同一个数出现的次数不等于 $2$ 的数据，就可以直接输出 NO 。

有题目可以得到一个显然的结论：如果有两块多米诺骨牌都包含同一个数，那它们一定不在同一个集合中。

有这样的关系，还有这题两个集合，就很容易想到二分图。

可以把多米诺骨牌的编号作为节点编号，由于每个数出现两次，所以对于包含同一个数的第 $i$ 块和第 $j$ 块多米诺骨牌（$1 \le i,j \le n$ 且 $i \neq j$），在编号为 $i$ 的节点和编号为 $j$ 的节点之间连双向边。很明显相邻的两个点不会分到同一个集合中。

建好图后就可以用染色法跑一遍二分图判定。具体来说就是用黑白两种颜色标记图中的点，如果一个点被标记了，那它周围的点都要被标记上相反的颜色（在此题中就表示分到另一个集合）。如果染色过程中出现矛盾，就说明无法按照题目要求分成两个集合，所以输出 NO ，反之输出 YES 。此题解用 bfs 实现。

Code

#include<bits/stdc++.h>
#define maxn 200010
#define pii pair<int,int>
#define fi first
#define sc second
using namespace std;
int T,n,c[maxn],flag; pii a[maxn];
vector<int> g[maxn],p[maxn];
bool check(){ //二分图判定（染色法）
	queue<int> q;
	memset(c,0,sizeof(c)); //初始时都没有颜色
	for(int i=1;i<=n;i++){
		if(!c[i]){ //如果没有被染过色
			q.push(i); c[i]=1; //放入队列，先染上颜色1
			while(!q.empty()){ //bfs枚举相邻的点
				int x=q.front(); q.pop();
				for(int j=0;j<g[x].size();++j){
					int y=g[x][j];
					if(!c[y]){ //没染过色
						q.push(y);
						if(c[x]==1) c[y]=2;
						else c[y]=1; //染上相反的颜色并放入队列
					}
					else if(c[y]==c[x]) return false; //出现矛盾，不是二分图
				}
			}
		}
	}
	return true;//染色成功，是二分图
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n); flag=0;
		for(int i=1;i<=n;++i){
			g[i].clear(); p[i].clear(); //多测不清空，爆零两行泪
		}
		for(int i=1;i<=n;++i){
			scanf("%d%d",&a[i].fi,&a[i].sc);
			p[a[i].fi].push_back(i);
			p[a[i].sc].push_back(i); //p[i]表示包含i的多米诺骨牌的编号
		}
		for(int i=1;i<=n;++i)
			if(p[i].size()!=2) flag=1; //判定是否所有数都出现2次
		if(flag){
			puts("NO"); continue;
		}
		for(int i=1;i<=n;++i){
			g[p[i][0]].push_back(p[i][1]);
			g[p[i][1]].push_back(p[i][0]); //建图
		}
		if(check()) puts("YES"); //二分图判定
		else puts("NO");
	}
	return 0;
}