uva10004Bicoloring-WA

84 阅读 0 评论 56 点赞

我是靠谱客的博主健康奇迹，最近开发中收集的这篇文章主要介绍uva10004Bicoloring-WA，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法：既然只有两种颜色，那么可以将所有的点分到两个集合中，假定：集合A是红色，集合B是黑色，而且相同集合中的点之间不能有边，不同集合中的点必须有边，即对于集合A中的任意一个点都能连到集合B中，但是这一点不必担心，因为这是强连通图，任意一个点都不会孤立的。只要看前一个条件了，SO：我在读入每一条边时就将两个顶点分别放在两个集合中，下次再读入一条边，如果发现有个顶点出现在集合A（B）中，就将另一个顶点放入B（A）中，如果发现有一个顶点同时出现在A和B中，就不能not bicoloring.

WA:表面上看是对的，但是例如读入<0 1> 的话，A中有【0】，B中有【1】，再读入<3 4>时，算法就会将A修改为【0,3】，B修改为【1,4】，此时就规避了A【0,4】，B【1,3】这种可能了，当然会忽略很多种可能。

WA代码：

//10004Bicoloring WA
//2013-4-18
/*
0
3
.....
在出现<3,4>的时候算法中假定3涂1号色，4涂 -1号色，如果这样最终没有出现符合题意的结果
1
4
就能代表真的没有可能出现吗？显然不对，比如可能出现 4涂1号色，3涂
-1号色时出现可能情况。
*/
#include<iostream>
#include<vector>
using namespace std;
class Bicoloring{
private:
vector <int> node;
bool BICOLORABLE;
public:
void initial();
void readCase(int);
void computing();
void outResult();
};
void Bicoloring::initial(){
node.clear();
BICOLORABLE = false;
}
void Bicoloring::readCase(int m){
int n1,n2;
while(m--){
cin >> n1 >> n2;
node.push_back(n1);
node.push_back(n2);
}
}
void Bicoloring::computing(){
int temp[205]={0};
int n1,n2,i;
for(i = 0; i < node.size(); i=i+2){
n1 = node[i]; n2 = node[i+1];
if(temp[n1] == 0 && temp[n2] == 0){temp[n1] = 1;temp [n2] = -1;}
if(temp[n1] == 0 && temp[n2]) {temp[n1] = - temp[n2];}
if(temp[n2] == 0 && temp[n1]) {temp[n2] = - temp[n1];}
if(temp[n1] && temp[n2]){
if(temp[n1] == temp[n2]) break;
}
//cout << "i = " <<i <<endl;
}
if(i == node.size()) BICOLORABLE = true;
}
void Bicoloring::outResult(){
if(BICOLORABLE) cout << "BICOLORABLE." <<endl;
else cout << "NOT BICOLORABLE." <<endl;
}
int main(){
Bicoloring b;
int n,m;
cin >> n;
while(n--){
if(cin >> m && m ){
b.initial();
b.readCase(m);
b.computing();
b.outResult();
}
}
return 0;
}