二部图确定 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 给定一个具有n个顶点的图. 要给图上每一个顶点染色, 而且要使相邻的顶点颜色不同. 

能否最多用2种颜色进行染色. 没有重边和闭环.

即二分图问题.

使用深度优先搜索(dfs), 把顶点染成c, 然后相邻边染成-c.

假设相邻边被染色过, 且同样, 则图不是二分图; 假设全部边都被染色, 而且互不同样, 则是二分图.

进行多次搜索, 避免非连通图.

代码:

/*

 * CppPrimer.cpp

 *

 *  Created on: 2014.7.27

 *      Author: Caroline

 */

/*eclipse cdt*/

#include <stdio.h>

#include <vector>

using namespace std;

class Program {

	static const int MAX_V = 100;

	/*vector<int> G[MAX_V] = {{1,3}, {0,2}, {1,3}, {0,2}};

	int V = 4;*/

	vector<int> G[MAX_V] = {{1,2}, {0,2}, {0,1}};

	int V = 3;

	int color[MAX_V] = {0};

	bool dfs(int v, int c) {

		color[v] = c;

		for (size_t i=0; i<G[v].size(); ++i) {

			if (color[G[v][i]] == c) return false;

			if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;

		}

		return true;

	}

public:

	void solve() {

		for (int i=0; i<V; i++) {

			if (color[i] == 0) {

				if(!dfs(i,1)) {

					printf("result = No\n");

					return;

				}

			}

		}

		printf("result = Yes\n");

	}

};

int main (void)

{

	Program iP;

	iP.solve();

	return 0;

}

输出:

result = No