牛客国庆集训派对Day3 J Graph Coloring I

本文主要是介绍牛客国庆集训派对Day3 J Graph Coloring I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：点击打开链接

题意：判断一个图是否能用两种颜色染色，满足相邻点的颜色不同。

分析：可以直接对图进行染色，如果发现当前点的颜色与已经染色的相邻点相同，则存在奇环（环山点的总数为奇数）。也可以判断是否为二分图，因为二分图与奇环互斥。

证明：假设二分图中的环是奇数环。

设一个环，x1，x2，x3，，，，x(2k-1)，k>=1且为整数。相邻两点有边连接，x1与x(2k-1)相连。

由二分图定义可知：x1与x2分别在X集合和Y集合，由于x2与x3的关系可知x3在X集合，则x4在Y集合，以此类推，可得奇数点在X集合，偶数点在Y集合，那么点x(2k-1)则在X集合中，即与x1同为一个集合，但有之间假设的x1与x(2k-1)有连边，那么此时就与二分图定义不符，这二分图中的环不可能是奇数环。

只需要DFS对无向图进行二分染色，如果不满足二分图，即我们找到了顶点v和u染色错误。vu顶点构成的这条路径一定是一个奇环。根据dfs的顺序回溯即可还原这条路径。

代码一：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, m;
bool vis[N];
vector<int> g[N];
int a[N], ans[N], cnt;
bool flag;
int st;
void DFS1(int x, int y)
{vis[x] = 1;a[x] = y;for(int i = 0; i < g[x].size(); i++)if(!vis[g[x][i]])DFS1(g[x][i], (y + 1) % 2);else if(a[g[x][i]] == y)flag = 0, st = g[x][i];
}
void DFS2(int x)
{if(flag) return;ans[++cnt] = x;vis[x] = 1;for(int i = 0; i < g[x].size(); i++)if(!vis[g[x][i]])DFS2(g[x][i]);else if(g[x][i] == st && cnt % 2 != 0)flag = 1;if(!flag) cnt--;
}
int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}memset(vis, 0, sizeof(vis));flag = 1;DFS1(1, 0);if(flag){printf("0\n");for(int i = 1; i <= n; i++)printf("%d ", a[i]);printf("\n");}else{flag = 0;memset(vis, 0, sizeof(vis));DFS2(st);printf("%d\n", cnt);for(int i = 1; i <= cnt; i++)printf("%d ", ans[i]);printf("\n");}
}

代码二：

#include<algorithm>
#include<iostream>
#include<fstream>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iomanip>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cctype>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
const int maxn = 3e5+10;
vector<int> ways[maxn];
int col[maxn],path[maxn],n,m,root;
vector<int> ans;
bool flag;
inline void init() {memset(col,-1,sizeof(col));memset(path,-1,sizeof(path));ans.clear();flag = true;for(int i=0;i<maxn;i++) ways[i].clear();
}
inline void addedge(int u,int v) {ways[u].push_back(v);ways[v].push_back(u);
}
void dfs(int rt,int c) {if(!flag) return ;col[rt] = c;for(int i=0;i<ways[rt].size();i++) {if(!flag) return;if(col[ways[rt][i]] == -1) {path[ways[rt][i]] = rt;dfs(ways[rt][i],c^1);}else {if(col[ways[rt][i]] == c) {path[ways[rt][i]] = rt;flag = false;root = ways[rt][i];return;}}}
}
int main()
{while(~scanf("%d%d",&n,&m)) {init();for(int i=0,u,v;i<m;i++) {scanf("%d%d",&u,&v);addedge(u,v);}dfs(1,0);if(flag) {printf("0\n");for(int i=1;i<n;i++) printf("%d ",col[i]);printf("%d\n",col[n]);}else {int now = path[root];ans.push_back(root);while(root != now) {ans.push_back(now);now = path[now];}int k = ans.size();printf("%d\n",k);for(int i=0;i<k-1;i++) printf("%d ",ans[i]);printf("%d\n",ans[k-1]);}}return 0;
}

这篇关于牛客国庆集训派对Day3 J Graph Coloring I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！