1var assert = require('assert');
2
3var twoColorGraph = function (N, dislikes) {
4  if (!dislikes.length) return true;
5  const graph = new Map();
6  const marked = Array(N + 1).fill(0);
7  const stack = [];
8
9  // create adjacency list
10  for (let [a, b] of dislikes) {
11    graph.set(a, (graph.get(a) || new Set()).add(b));
12    graph.set(b, (graph.get(b) || new Set()).add(a));
13  }
14
15  marked[0] = 1;
16  stack.push([dislikes[0][0], 1]);
17
18  while (stack.length) {
19    const [node, mark] = stack.pop();
20    marked[node] = mark;
21
22    if (graph.has(node)) {
23      const neighbors = graph.get(node);
24
25      for (let vertex of neighbors) {
26        if (marked[vertex] === mark) return false;
27        if (marked[vertex] === 0) stack.push([vertex, ~mark]);
28      }
29    }
30
31    if (stack.length === 0 && marked.includes(0)) {
32      for (let i = 1; i < marked.length; i++) {
33        if (graph.has(i) && marked[i] === 0) {
34          stack.push([i, 1]);
35          break;
36        }
37      }
38    }
39  }
40  return true;
41};
42
43try {
44  N = 4;
45  dislikes = [
46    [0, 1, 0, 1],
47    [1, 0, 1, 0],
48    [0, 1, 0, 1],
49    [1, 0, 1, 0],
50  ];
51  assert.equal(twoColorGraph(N, dislikes), true);
52
53  console.log('PASSED: ' + 'First Test');
54} catch (err) {
55  console.log(err);
56}
57
58try {
59  N = 4;
60  dislikes = [
61    [0, 1, 1, 1],
62    [1, 0, 0, 0],
63    [0, 1, 0, 1],
64    [1, 0, 1, 0],
65  ];
66  assert.equal(twoColorGraph(N, dislikes), true);
67
68  console.log('PASSED: ' + 'Second Test');
69} catch (err) {
70  console.log(err);
71}
72
73try {
74  N = 4;
75  dislikes = [
76    [1, 1, 0, 1],
77    [1, 0, 1, 0],
78    [0, 1, 0, 1],
79    [1, 0, 1, 0],
80  ];
81  assert.equal(twoColorGraph(N, dislikes), false);
82
83  console.log('PASSED: ' + 'Third Test');
84} catch (err) {
85  console.log(err);
86}