aboutsummaryrefslogtreecommitdiff
path: root/graph_bipartite.cpp
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() {}