886 Possible Bipartition

题目

886 Possible Bipartition

题解

题目要求检验是否能够把N个人分成两组，使得每个人不会跟不喜欢的人在同一个组里。 若以人作为顶点，不喜欢的关系作为边，那么我们可以为输入数据构造一个图，检验的结果就等价于验证该图是否为一个二分图。因为不喜欢的关系是双向的，构造的图必须是无向图，否则可能会出现A不喜欢B，B却喜欢A的奇怪现象，从而导致错误的验证结果。

要验证一个无向图是否为二分图，一个简单的方法是，利用深度优先遍历，交替地用两个小组号码对图进行标记。一个图不是二分图，当且仅当出现了两个相连（互相不喜欢）的顶点（人）拥有同样的分组的情况。因此，我们只要在利用深度优先遍历进行交替标记的过程中对邻接当前顶点的每一个顶点进行小组号码的检查，即可验证该图是否为二分图。

代码

class Solution {
public:
	bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
		vector<bool> group1(N + 1, false);
		vector<bool> group2(N + 1, false);

		map<int, vector<int>> graph;
		for (size_t i = 0; i < dislikes.size(); i++) {
			int v1 = dislikes[i][0];
			int v2 = dislikes[i][1];
			graph[v1].push_back(v2);
			graph[v2].push_back(v1);
		}

		vector<bool> visited(N + 1, false);
		for (size_t i = 1; i < visited.size(); i++)
		{
			if (!visited[i]) {
				if (!explore(graph, i, visited, group1, group2, 1)) {
					return false;
				}
			}
		}
		return true;
	}
private:
	bool explore(map<int, vector<int>>& graph, int current, vector<bool> &visited,
		vector<bool> &group1, vector<bool>& group2, int group) {
		visited[current] = true;
		if (group == 1) {
			group1[current] = true;
			group = 2;
		}
		else {
			group2[current] = true;
			group = 1;
		}

		for (size_t i = 0; i < graph[current].size(); i++)
		{
			int next = graph[current][i];
			if ((group1[current] && group1[next]) || (group2[current] && group2[next])) {
				return false;
			}
			if (!visited[next]) {
				if (!explore(graph, next, visited, group1, group2, group)) {
					return false;
				}
			}
		}
		return true;
	}
};