本文主要是介绍UVa 10004: Bicoloring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题要我们判断所给图是否可以用两种颜色进行染色，即"二染色“。已知所给图一定是强连通图。
分析之：
若图中无回路，则该图是一棵树，一定可以二染色。
若图中有回路，但回路有偶数个节点，仍然可以二染色。
仅当图中存在回路且回路有奇数个节点时，不能二染色。
具体实现细节我在代码中给出了详细的注释，我的解题代码如下：
/*
关键在于：当且仅当存在奇回路时，无法二染色
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
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; i++)if(adj[i][sour] && !vis[i]) return 1-find(i,obj);
}int main()
{int ta,tb;while(cin >> n && n!=0){cin >> l;memset(adj,0,sizeof(adj));memset(set,0,sizeof(set));int ok=1;for(int i=0; i<l; i++){cin >> 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<n; j++) if(set[j]==set[tb]) //输入的相邻两点所在集合不同，且并未产生偶节点数的回路，则将其中一集合的序号全部改为与另一集合相同set[tb]=set[ta];}}else if(!set[ta] && !set[tb]) //输入的两点原先均未标记所在集合，则标记之{set[ta]=set[tb]=ta+1; //没有使用=ta是因为如果那样，ta=0时set[ta],set[tb]将不产生变化}else if(!set[ta]) //只有ta未标记，则用tb标记ta{set[ta]=set[tb];}else if(!set[tb]) //同上{set[tb]=set[ta];}adj[ta][tb]=adj[tb][ta]=1;}}if(ok) cout << "BICOLORABLE.\n";else cout << "NOT BICOLORABLE.\n";}return 0;
}
这篇关于UVa 10004: Bicoloring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
