题意
\(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;
}