10004 - Bicoloring（BFS）

本文主要是介绍10004 - Bicoloring（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：10004 - Bicoloring

题目大意：将给定的图的节点染色，颜色只有两种，并且要求相邻的节点颜色不同，且无向图里面没有自环且是强连通的；

解题思路：因为是强连通的，所以用BFS可以访问到每个节点，并且相邻节点还可以染成不同的颜色。当染色冲突时，就说明这个图不可以二染色，如果顺利的都染色了，没有冲突，这个图就可以二染色。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;int v, e;
const int N = 205;int G[N][N], color[N];queue<int> q;int bfs (int t) {color[t] = 1;q.push(t);while(!q.empty()) {t = q.front();q.pop();for(int i = 0; i < v; i++) {if(G[t][i] && !color[i]) {color[i] = - color[t];q.push(i);}else  {if(G[t][i]) if(color[i] + color[t] != 0)return 0;}}}return 1;
}int main() {while(scanf("%d", &v) , v ) {memset(G, 0, sizeof(G));memset(color, 0, sizeof(color));scanf("%d", &e);int i, x, y;for(i = 0; i < e; i++) {scanf("%d%d", &x, &y);G[x][y] = 1;G[y][x] = 1;}if(bfs(x))printf("BICOLORABLE.\n");elseprintf("NOT BICOLORABLE.\n");while(!q.empty()) {q.pop();}}return 0;}

这篇关于10004 - Bicoloring（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---