UVa 10004: Bicoloring

这道题要我们判断所给图是否可以用两种颜色进行染色，即"二染色“。已知所给图一定是强连通图。

分析之：

若图中无回路，则该图是一棵树，一定可以二染色。

若图中有回路，但回路有偶数个节点，仍然可以二染色。

仅当图中存在回路且回路有奇数个节点时，不能二染色。

具体实现细节我在代码中给出了详细的注释，我的解题代码如下：

/*
关键在于：当且仅当存在奇回路时，无法二染色
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;int adj[200][200];	//邻接矩阵
int set[200];	//标记图中点所在集合序号
int vis[200];	//标记find中是否已搜索过该点
int n,l;int find(int sour, int obj)
{//在图上从点sour出发搜索obj，如果两者距离为偶返回0，为奇返回1vis[sour]=1;if(sour==obj) return 0;for(int i=0; i> n && n!=0){cin >> l;memset(adj,0,sizeof(adj));memset(set,0,sizeof(set));int ok=1;for(int i=0; i> ta >> tb;if(ok){if(set[ta] && set[tb])	//输入的相邻两点原先就在某个集合中{if(set[ta]==set[tb])	//输入的相邻两点所在集合相同，则用find搜索{memset(vis,0,sizeof(vis));if(!find(ta,tb)) { ok=0;}	//若返回0，则ta，tb两点将构成奇数个节点的回路，无法二染色}else{for(int j=0; j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！