aboutsummaryrefslogtreecommitdiff
path: root/is_graph_biparite.cpp
blob: 3f2f853a0eb2b0660718d598f029d33cce2dc489 (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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 785. Is Graph Bipartite?
#include "leetcode.h"

/*
 * there is an undirected graph with 'n' nodes, where each node is numbered
 * between 0 and 'n - 1'. you are given a 2d array 'graph' where 'graph[u]' is
 * an array of nodes that node 'u' is adjacent to. more formally, for each 'v'
 * in 'graph[u]', there is an undirected edge between node 'u' and node 'v'. the
 * graph has the following properties:
 * - there are no self-edges ('graph[u]' does not contain 'u')
 * - there are no parallel edges ('graph[u]' does not contain duplicate values)
 * - if 'v' is in 'graph[u]', then 'u' is in 'graph[v]' (the graph is
 * undirected)
 * - the graph may not be connected, meaning there may be two nodes 'u' and 'v'
 * such that there is no path between them a graph is bipartite if the nodes can
 * be partitioned into two independent sets 'A' and 'B' such that every edge in
 * the graph connects a node in set 'A' and a node in set 'B'. return true if
 * and only if the graph is bipartite.
 */

class Solution {
public:
  bool isBipartite(vvd(int) & graph) {
    int n = graph.size();
    vector<int> colour(n);
    queue<int> q;
    for (int i = 0; i < n; i++) {
      if (colour[i])
        continue;
      colour[i] = 1;
      for (q.push(i); !q.empty(); q.pop()) {
        int curr = q.front();
        for (int neighbour : graph[curr]) {
          if (!colour[neighbour]) {
            colour[neighbour] = -colour[curr];
            q.push(neighbour);
          } else if (colour[neighbour] == colour[curr])
            return false;
        }
      }
    }
    return true;
  }
};

int main() {
  Solution obj;
  vvd(int) g1 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
  vvd(int) g2 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
  printf("%d\n", obj.isBipartite(g1)); // expect: 0
  printf("%d\n", obj.isBipartite(g2)); // expect: 1
}