LeetCode 785 Is Graph Bipartite?
概述
https://leetcode.com/problems/is-graph-bipartite/
递归法
拿到题目，感觉挺简单的，直接遍历图，遍历过程中设置标记，一共有两种标记，设置一个节点的邻居节点为与之不同的另一种标记。
如果出现已标记的节点不兼容则其非二分图。
实现过程中，不要一个数组承担多个作用，例如用 mark 同时记录是否访问过和设置的颜色，很容易实现错。
class Solution {
public:
vector<bool> visited;
vector<bool> mark;
vector<vector<int>> graph;
bool ans = true;
bool isBipartite(vector<vector<int>>& graph) {
vector<bool> visited(graph.size(), false);
vector<bool> mark(graph.size(), false);
this->graph = graph;
this->visited = visited;
this->mark = mark;
for (int i = 0; i < graph.size(); i ++) {
if (!visited[i]) helper(i);
}
return ans;
}
void helper(int i) {
if (!ans) return;
visited[i] = true;
for (auto n : graph[i]) {
if (visited[n]) {
if (mark[n] == mark[i]) {
ans = false;
return;
}
} else {
mark[n] = !mark[i];
helper(n);
}
}
}
};