UVa 10004 Bicoloring

題意：
       只有兩種顏色，兩個相鄰的點必須顏色不同，給定一個graph，判斷該graph是否能符合上述條件。

想法：
       用BFS走遍所有的點，走過的點將它編號為1或2，如果下一個點還沒走過，將它標上和現在這個點不一樣的編號，如果下一個已經走過，而編號和現在這個點一樣，回傳false，否則當BFS搜索完，回傳true。

	#include <cstdio>
	#include <queue>
	#include <vector>
	using namespace std;
	int N,I;
	vector<int> toPoint[205];
	bool BFS(int Start)
	{
	queue<int> Q;
	Q.push(Start);
	int visit[205] = {0};
	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();
	for (int &nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	Q.push(nxt);
	if (visit[cur] == 1) visit[nxt] = 2;
	else visit[nxt] = 1;
	}
	else if (visit[nxt] == visit[cur])
	return false;
	}
	}
	return true;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d", &N)) {
	if (!N) break;
	for (auto &v : toPoint) v.clear();
	scanf("%d", &I);
	int p1, p2;
	for (int i=0; i<I; ++i) {
	scanf("%d %d", &p1, &p2);
	toPoint[p1].push_back(p2);
	toPoint[p2].push_back(p1);
	}
	printf("%s\n", BFS(p1) ? "BICOLORABLE." : "NOT BICOLORABLE.");
	}
	}

view raw [UVa] 10004 Bicoloring.cpp hosted with ❤ by GitHub