Bicoloring

183 阅读 0 评论 121 点赞

我是靠谱客的博主包容星星，这篇文章主要介绍Bicoloring，现在分享给大家，希望可以做个参考。

这个是我在一个人的博客上看到的算法，用的是图和深度遍历算法。我自己照他的想法写了程序，发现是可以的。

// Bicoloring.cpp : Defines the entry point for the console application. // #include "stdafx.h" const int MAX=200; using namespace std; int graph[MAX][MAX]; int colored[MAX]; bool visited[MAX]; int _tmain(int argc, _TCHAR* argv[]) { bool DFS(int n, int start); int point=0; while(cin>>point) { if(point==0)break; else { for(int i=0;i<point;++i) { for(int j=0;j<point;++j)graph[i][j]=0; } int edge,v1,v2; cin>>edge; for(int i=0;i<edge;++i) { cin>>v1>>v2; graph[v1][v2]=1; graph[v2][v1]=1; } for(int i=0;i<point;++i) { colored[i]=0; visited[i]=false; } colored[0]=1; if(DFS(point,0))cout<<"BICOLORABLE"<<"/n"; else cout<<"NOT BICOLORABLE"<<"/n"; } } system("pause"); return 0; } bool DFS(int n, int start) { for(int i=0;i<n;++i) { if((graph[start][i]==1)&&(visited[i]==false)) { visited[start]=true; if(colored[start]==1) { if(colored[i]==0)colored[i]=2; else if(colored[i]==1)return false; } else { if(colored[i]==0)colored[i]=1; else if(colored[i]==2)return false; } DFS(n,i); } } return true; }