Graph problems

Connected components — how many separate "islands" exist

function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { graph[u].push(v); graph[v].push(u); }

  const visited = new Set();
  let components = 0;

  for (let node = 0; node < n; node++) {
    if (visited.has(node)) continue; // already covered by an earlier DFS
    components++;
    // flood-fill everything reachable from "node" into "visited"
    const stack = [node];
    visited.add(node);
    while (stack.length) {
      const curr = stack.pop();
      for (const next of graph[curr]) {
        if (!visited.has(next)) { visited.add(next); stack.push(next); }
      }
    }
  }
  return components;
}

The pattern generalizes directly to grid problems ("number of islands"): each land cell is a node, each adjacent land cell is an edge — same flood-fill, just walking up/down/left/right instead of an adjacency list.

Cycle detection — the rule differs by directed vs undirected

// undirected: skip the edge back to where you just came from
function hasCycleUndirected(graph, node, visited, parent) {
  visited.add(node);
  for (const next of graph[node]) {
    if (!visited.has(next)) {
      if (hasCycleUndirected(graph, next, visited, node)) return true;
    } else if (next !== parent) {
      return true; // hit an already-visited node that ISN'T where we came from
    }
  }
  return false;
}

// directed: need a THIRD state — "on the current recursion path"
function hasCycleDirected(graph, n) {
  const state = new Array(n).fill(0); // 0=unvisited, 1=in-progress, 2=done

  function dfs(node) {
    state[node] = 1;
    for (const next of graph[node]) {
      if (state[next] === 1) return true;       // back-edge to an in-progress node = cycle
      if (state[next] === 0 && dfs(next)) return true;
    }
    state[node] = 2;
    return false;
  }

  for (let i = 0; i < n; i++) {
    if (state[i] === 0 && dfs(i)) return true;
  }
  return false;
}

That three-state trick (unvisited / in-progress / done) on a directed graph is the exact same idea behind detecting a circular dependency — "in-progress" means "currently on the stack of things depending on each other," and looping back to one of those is the cycle.

Bipartite check — can you 2-color it with no clashes?

function isBipartite(graph) {
  const color = new Array(graph.length).fill(0); // 0=uncolored, 1 or -1 = the two colors

  for (let start = 0; start < graph.length; start++) {
    if (color[start] !== 0) continue;
    color[start] = 1;
    const queue = [start];

    while (queue.length) {
      const node = queue.shift();
      for (const next of graph[node]) {
        if (color[next] === 0) {
          color[next] = -color[node]; // force the opposite color
          queue.push(next);
        } else if (color[next] === color[node]) {
          return false; // a neighbor shares my color — contradiction
        }
      }
    }
  }
  return true;
}

Recognizing which one an unseen problem wants

• "How many groups/islands/provinces" → connected components
• "Can these all be completed" / "is there a circular dependency" → cycle detection (directed, usually — think course prerequisites)
• "Can you split into two groups with no conflicts" / "is this graph 2-colorable" → bipartite check
• All three reuse the exact same BFS/DFS skeleton from the previous chapter — the only new part is what you track while visiting