Split Into Two Sets CodeForces - 1702E
Polycarp 有一副有 n 张牌的(数字 n 为偶数) 多米诺骨牌. 每张多米诺骨牌上写有两个在 1 到 n 之间的数字.
请问能否把骨牌分成两副，使得每一副骨牌中都没有重复的数字?
所有骨牌都必须被分到其中一副中，且两副骨牌的数量相同。
例如, 假如他有 4 张多米诺骨牌: {1,4}, {1,3}, {3,2} 和 {4,2}，
可以将第 1,3 张骨牌分给第一副 ({1,4}和 {3,2})，然后第 2,4 张分给第二副({1,3}和 {4,2})。
提示：可能出现 {1,2}, {2,3}, {3,1}, {4,1} 这样的 4 张骨牌，显然这样的一副骨牌无法按条件分成两副
Input
第一行包含一个整数 t(1≤t≤1e4) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个偶数 n(2≤n≤2e5) — 多米诺骨牌的数量。
下一个 n 行包含成对的数字 ai,bi — 描述多米诺骨牌上的数字。
保证所有测试用例中 n 的总和不超过 2e5。
Output
对于每个测试用例打印：
如果可以将 n 个多米诺骨牌分为两组，以便每组多米诺骨板上的数字不同，输出 "YES"；否则输出 "NO"。
Sample Input
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
Sample Output
YES
NO
NO
YES
YES
NO
分析
考察内容：二分图的判定
二分图：是指可以将图中点集分为相连的两部分，且每部分内部互不相连。
判断一个图是否为二分图，等价于 判断图中是否有长度为奇数的环，等价于 图是否可以被二染色。
如果没有奇环，则图为二分图。
可以使用染色法，先该点染红，则与之相连的各个邻居都染蓝，邻居的邻居继续染红，直到所有点都染完，就是一个二分图；如果出现染色冲突，则不是二分图。
图染色问题：问是否可以给每个点染上一种颜色，对于所有边老说，边上的两个点颜色均不同。
- 下列程序出现问题，怀疑是多组数据导致的，但是我已经初始化了，想不到问题在哪里
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10,INF=0x3f3f3f3f;
vector<int> G[N], color(N);
int is_two_colorable=1;
void dfs(int u,int c){
for(vector<int>::iterator it=G[u].begin(); it!=G[u].end(); it++){
int v=*it, nc=3-c; // u 的邻居 v 应该染上的色 nc
if(color[v]){ // 邻居染过色
if(color[v]!=nc){ // 发生冲突
is_two_colorable=0; return;
}
}else{ // 给它染色
color[v] = nc;
dfs(v, color[v]);
}
}
}
int main(){
freopen("data.in", "r", stdin);
int t,n,u,v; scanf("%d", &t);
while(~scanf("%d", &n)){
for(int i=0; i<N; i++) G[i].clear();
//memset(G, 0, sizeof(G));
color.clear(), is_two_colorable=1;
for(int i=1; i<=n; i++) scanf("%d%d", &u,&v),
G[u].push_back(v), G[v].push_back(u);
for(u=1; u<=n; u++){
if(!color[u]){ // u 还未染色
color[u]=1, dfs(u, color[u]);
}
}
printf("%s\n", is_two_colorable ? "YES" : "NO");
}
return 0;
}