建设网站域名有了还要什么,浏览器在线打开网页,深圳网站建设服务找哪家,md5(wordpress)来源#xff1a;牛客网#xff1a;
题目描述
修修在黑板上画了一些无向连通图#xff0c;他发现他可以将这些图的结点用两种颜色染色#xff0c;满足相邻点不同色。 澜澜不服气#xff0c;在黑板上画了一个三个点的完全图。修修跟澜澜说#xff0c;这个图我能找到一个简…来源牛客网
题目描述
修修在黑板上画了一些无向连通图他发现他可以将这些图的结点用两种颜色染色满足相邻点不同色。 澜澜不服气在黑板上画了一个三个点的完全图。修修跟澜澜说这个图我能找到一个简单奇环。 澜澜又在黑板上画了一个n个点m条边的无向连通图。很可惜这不是一道数数题修修做不出来了。 澜澜非常得意作为一位毒瘤出题人有了好题当然要跟大家分享于是他把这道题出给你做了。 输入描述: 第一行两个整数n,m (1≤ n,m≤ 3*105)接下来m行每行两个整数ai,bi表示一条边 (1≤ ai,bi≤ n)。 保证图连通并且不存在重边和自环。 输出描述:
示例1 输入 复制
3 2
1 2
1 3输出 复制
0
0 1 1示例2 输入 复制
3 3
1 2
1 3
2 3输出 复制
3
1 2 3题解
本题可以浓缩成两个问题能否被01染色以及是否有奇环我们仔细想想会发现其实这两个问题是互相矛盾的也就是能01染色就不存在奇环反之亦然。所以题目中同时可行以及都不可行是不存在的 我们可以先01染色当发现染不动时说明就出现奇环了记录当前不能再染的点也就是染色矛盾的点染色途中是记录路径的所以输出奇环时输出路径即可 额。。代码没有全对。。。
代码
#include cstdio
#include algorithm
#include cstring
#include vector
using namespace std;
const int N3*1e550;
vectorint g[N];
int color[N];
int pre[N];
vectorint res;
bool flag;
int root;
void init(){memset(color,-1,sizeof(color));memset(pre,-1,sizeof(pre));flagtrue;
}
void dfs(int v,int c){if(!flag){return;}color[v]c;for(int i0;ig[v].size();i){if(!flag){return;}pre[g[v][i]]v;if(color[g[v][i]]-1){dfs(g[v][i],c^1);}else{//不是二分图if(color[g[v][i]]c){flagfalse;//说明奇环就出现在这里rootg[v][i];return;}}}
}
int main(void){init();int n,m;int u,v;scanf(%d%d,n,m);for(int i0;im;i){scanf(%d%d,u,v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);if(flag){printf(0\n);for(int i1;in;i){printf(%d ,color[i]);}printf(%d\n,color[n]);}else{int nowpre[root];res.push_back(root);while(root!now){res.push_back(now);nowpre[now];}int cntres.size();printf(%d\n,cnt);for(int i0;icnt-1;i){printf(%d ,res[i]);}printf(%d\n,res[cnt-1]);}return 0;
}
