本文主要是介绍uva10004 Bicoloring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：对于无向强连通图，判断是否可以用两种颜色图完所有顶点，要求相邻的两个顶点颜色不同。
解法：运用到dp的思想，使用BFS模拟涂色的过程，并且实时的检测。
代码：
//uva10004 Bicoloring
//AC By Warteac
//2013-4-18
/*
dp的思想，运用BFS，并且模拟涂色的过程并且时事地检测
*/
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
class Bicoloring{
private:
int node[201][201];
bool BICOLORABLE;
int start;//开始点
int numOfNode;//顶点的个数
public:
void initial();
void readCase(int,int);
void computing();
void outResult();
};
void Bicoloring::initial(){
memset(node,0,sizeof(node));
BICOLORABLE = true;
start = 0;
numOfNode = 0;
}
void Bicoloring::readCase(int n,int m){
int n1,n2;
numOfNode = n;
while(m--){
cin >> n1 >> n2;
node[n1][n2] = 1;
node[n2][n1] = 1;
}
start = n1;//随便找个开始点
}
void Bicoloring::computing(){
queue <int> q;
int color[201]={0},c = 1;
int qsize,t;
q.push(start);
color[start] = c;
qsize = q.size();
while(!q.empty()){
qsize = q.size();
c = -c ;//cout <<"-------------------" <<endl;
while(qsize--){
t = q.front(); //cout << "t = " <<t <<endl;
q.pop();
for(int i = 0; i < numOfNode ;i++){
if(node[t][i]){//cout <<" i = " <<i << " color[i] = " <<color[i]<<endl;
if(color[i] == 0){
color[i] = c;//cout <<" i = " <<i << " color[i] = " <<color[i]<<endl;
}else if(color[i] != c){//如果已经涂过色，并且和将要图的颜色不同，NOT BICOLORABLE.
BICOLORABLE = false;
return;
}
q.push(i);
for(int j = 0; j < numOfNode; j++)//将回路切断，不许返回
node[j][t] = 0;
}
}
}
}
}
void Bicoloring::outResult(){
//cout << "numOfNode = " <<numOfNode<<endl;
//cout << "start = " << start <<endl;
if(BICOLORABLE) cout << "BICOLORABLE." <<endl;
else cout << "NOT BICOLORABLE." <<endl;
}
int main(){
Bicoloring b;
int n,m;
while(cin >> n && n){
cin >> m;
b.initial();
b.readCase(n,m);
b.computing();
b.outResult();
}
return 0;
}
这篇关于uva10004 Bicoloring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
