blob: b37972d969b881969c83247845e1114e5d535429 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include "leetcode.h"
class Solution {
public:
vector<int> vis, col;
bool isBipartite(vector<vector<int>> &graph) {
int n = graph.size();
vis.resize(n);
col.resize(n);
for (int i = 0; i < n; i++)
if (vis[i] == 0 && dfs(i, 0, graph) == false)
return false;
return true;
}
private:
bool dfs(int v, int c, vector<vector<int>> &graph) {
vis[v] = 1;
col[v] = c;
for (int child : graph[v])
if (vis[child] == 0) {
if (dfs(child, c ^ 1, graph) == false)
return false;
} else if (col[v] == col[child])
return false;
return true;
}
};
int main() {}
|