# Two Colorable - Graph

![](https://3743232000-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FHW2IQuh2PFpWJDvBz2FF%2Fuploads%2Fgit-blob-57962fe595a2b98913a2783955acefeb2d43cee6%2FScreenshot%202023-01-24%20at%200.51.21.png?alt=media)

* V + E, V

```jsx
let canColor;

function twoColorable(edges) {
  canColor = true;
  bfsAll(edges);
  return canColor;
}

function bfsAll(adjacencyList) {
  const colors = new Array(adjacencyList.length).fill(0);

  let components = 0;
  for (let i = 0; i <= adjacencyList.length; i++) {
    if (colors[i] !== 0) continue;

    components += 1;
    const vertex = i;
    colors[vertex] = components % 2 + 1; // extra work
    
    bfs(adjacencyList, vertex, colors);
  }
}

function bfs(adjacencyList, here, colors) {

  const q = [here];
  while (q.length > 0) {
    const here = q.shift();
    const hereColor = colors[here];
    const edges = adjacencyList[here];
    
    for (let i = 0; i < edges.length; i++) {
      const there = edges[i];
      if (hereColor === colors[there]) {
        canColor = false;
        return;
      }

      if (colors[there] !== 0) continue;
      colors[there] = hereColor === 1 ? 2 : 1;
      q.push(there);
    }
    
  }
}

// Do not edit the line below.
exports.twoColorable = twoColorable;
```