首页 > 代码库 > UVA 10004 Bicoloring（DFS染色）
UVA 10004 Bicoloring（DFS染色）
题意：
给N个点构成的无环无向图，并且保证所有点对都是连通的。
给每个点染色，要么染成黑要么染成白。问是否存在染色方案使得所有有边相连的点对颜色一定不一样。
是输出 BICOLORABLE 否则输出 NOT BICOLORABLE
思路：
从某点开始，直接进行染色，如果矛盾，返回false。
代码：
int n,l;vector<int> graph[205];int color[205];bool dfs(int u,int fa){ if(color[fa]==0) color[u]=1; else color[u]=0; int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(v!=fa){ if(color[v]==-1) dfs(v,u); else if(color[v]+color[u]!=1) return false; } } return true;}int main(){ int start; while(scanf("%d",&n)!=EOF,n){ scanf("%d",&l); rep(i,0,n-1) graph[i].clear(); mem(color,-1); color[n]=0; while(l--){ int u,v; scanf("%d%d",&u,&v); start=u; graph[u].push_back(v); graph[v].push_back(u); } bool yes=dfs(start,n); if(yes) puts("BICOLORABLE."); else puts("NOT BICOLORABLE."); }}
UVA 10004 Bicoloring（DFS染色）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。