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.

Number of provinces: when the graph arrives as a matrix

The flood-fill loop above assumed an adjacency list. A common variant hands you the graph as an adjacency matrix instead: n cities, and isConnected[i][j] === 1 when city i and city j are directly connected. A province is a group of cities joined directly or through other cities, which is exactly a connected component. The answer is the number of components.

Nothing new is needed except one change: there is no neighbour list to iterate, so the neighbours of city c are the columns in row c that hold a 1. Scanning a row costs O(n), and every city is scanned once, so this version takes O(n²) time. That is not a weakness of the code: with a matrix, O(n²) is simply the cost of reading the input.

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;
  for (let city = 0; city < n; city++) {
    if (visited[city]) continue; // an earlier search already reached it
    provinces++;
    visited[city] = true;
    const stack = [city];
    while (stack.length > 0) {
      const current = stack.pop();
      for (let other = 0; other < n; other++) { // a row of the matrix is the neighbour list
        if (isConnected[current][other] === 1 && !visited[other]) {
          visited[other] = true;
          stack.push(other);
        }
      }
    }
  }
  return provinces;
}

Dry run: isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

The answer is 2: cities 0 and 1 form one province, city 2 another. Three slips are common. The diagonal is 1 by convention (a city is connected to itself), so a city must be marked visited before its row is read, or it can be treated as its own unvisited neighbour. The matrix is symmetric, but do not read only half of it in a traversal: with edges 0-2 and 1-2, a search that looks only at columns after the current row cannot get from city 2 back to city 1, and counts two provinces instead of one. And there is no need to translate the matrix into an adjacency list first, since that costs another O(n²) and gives nothing back. We checked this against a union-find count on thousands of random symmetric matrices.

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.

Dry run: hasCycleDirected on the 3-node cycle 0→1→2→0

Node 0 never reaches state 2 ("done") — the call stack is still three deep inside it when the back-edge to it is found. That's exactly what "in-progress" is for: if 0 had already finished (state 2) before 2 ever looked at it, seeing it again would mean a second, unrelated path merged back in — not a cycle. Only a back-edge to something still open on the current path counts.

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;
}

Graph valid tree: connected, with no cycle

Given n nodes and a list of undirected edges, decide whether the graph is a tree: every node reachable from every other (one component) and no cycle. You already have both tools, a component count and a cycle check. But there is a shorter route, because a tree has a numeric fingerprint.

Start with a single node and no edges: connected, no cycle. Adding a node that attaches by one edge keeps it connected and cycle-free, so a tree with n nodes built this way has n - 1 edges. Any extra edge between two nodes already in the tree closes a cycle, and any missing edge leaves a node unreachable. So for a graph with n nodes and exactly n - 1 edges, "no cycle" and "connected" are the same statement: if it is connected, it cannot have a cycle, and if it has no cycle, it must be connected. Checking one of the two is enough, once the edge count is right.

function validTree(n, edges) {
  if (edges.length !== n - 1) return false; // a tree on n nodes has exactly n - 1 edges
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
  const seen = new Set([0]);
  const stack = [0];
  while (stack.length > 0) {
    const node = stack.pop();
    for (const next of graph[node]) {
      if (!seen.has(next)) {
        seen.add(next);
        stack.push(next);
      }
    }
  }
  return seen.size === n; // n - 1 edges and connected leaves no room for a cycle
}

Dry run: two inputs with n = 5 and four edges

The second input passes the count and fails the traversal: it has a cycle (1, 2, 3) and an isolated node (4), and the extra edge that made the cycle also took the place of the one that would have connected node 4. Both checks are needed, which is why the function does both. Its time is O(V + E), and, since the count test returns first, the traversal only runs when E = V - 1.

Edges arriving one at a time: the union-find pointer

Traversal answers questions about a graph you already hold. When the edges come one at a time and you must answer after each ("are these two already connected?", "did this edge create a cycle?", "how many groups now?"), re-running a DFS after every edge costs O(V + E) each time. A data structure built for exactly this is union-find (disjoint sets). It keeps each group as a tree of parent pointers and gives every group a single root that names it: find(x) follows the pointers up to the root, and union(a, b) joins the two groups by pointing one root at the other. Two nodes are connected exactly when their roots are equal.

That makes the cycle test almost free. An edge [u, v] closes a cycle exactly when u and v already share a root, because a path between them exists before the edge is added.

function validTreeUnionFind(n, edges) {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving: point at the grandparent as we climb
      x = parent[x];
    }
    return x;
  };
  for (const [u, v] of edges) {
    const rootU = find(u), rootV = find(v);
    if (rootU === rootV) return false; // already connected: this edge would close a cycle
    parent[rootU] = rootV; // merge the two groups
  }
  return true;
}

This is the same answer as the traversal version: with n - 1 edges and no edge closing a cycle, the n - 1 successful merges have joined all n nodes into one group. The line parent[x] = parent[parent[x]] (path halving) keeps the trees flat, so each find is, for practical purposes, constant time. The full structure, with union by size, the amortized cost and the harder variants (weighted ratios, parity, offline deletion) has its own chapter, Union-find.

Reachability: what can I get to from here

"Reachable" questions ask which nodes a traversal from a start can touch. Nothing in the traversal changes. What changes is the question you ask of the visited set at the end, and sometimes whether you may keep it at all.

Keys and rooms: is everything reachable?

There are n rooms, numbered from 0. Room 0 is unlocked. Each room holds a list of keys, and key k opens room k. Can you enter every room? That is a directed graph (the keys in room i are edges i → k), and the question is whether the search from node 0 reaches all n nodes.

function canVisitAllRooms(rooms) {
  const opened = new Set([0]); // room 0 is unlocked
  const stack = [0];
  while (stack.length > 0) {
    for (const key of rooms[stack.pop()]) {
      if (!opened.has(key)) {
        opened.add(key);
        stack.push(key);
      }
    }
  }
  return opened.size === rooms.length;
}

Dry run: rooms = [[1, 3], [3, 0, 1], [2], [0]]

The stack empties with three rooms open out of four, so the answer is false. Room 2 holds the only key to room 2 itself, so no room that can be entered gives you a way in. Time O(n + k) for k keys in total. Do not forget that a key can lead to a room you have already opened: without the opened set a loop of keys would run forever.

All paths from source to target

Now you want every route, not whether one exists. In a directed acyclic graph with nodes 0 to n - 1, list every path from node 0 to node n - 1. A path can share nodes with another, so a global visited set would wrongly block the second route to a node. Instead keep the current path, extend it before each recursive call, and take the last node off after the call returns. This is the same choose, explore, un-choose rhythm as backtracking, and in a DAG it needs no visited marking at all, since a path can never come back to a node it has used.

function allPathsSourceTarget(graph) {
  const target = graph.length - 1;
  const paths = [];
  const path = [0];
  function dfs(node) {
    if (node === target) {
      paths.push([...path]); // copy: path keeps changing after this
      return;
    }
    for (const next of graph[node]) {
      path.push(next); // choose
      dfs(next);
      path.pop(); // un-choose
    }
  }
  dfs(0);
  return paths;
}

Dry run: graph = [[1, 2], [3], [3], []]

The result is [[0, 1, 3], [0, 2, 3]]. Two traps. Pushing path itself instead of [...path] stores the same array each time, and since it is emptied again by the un-choose steps you end up with a list of arrays that are all just [0]. And the cost is not O(V + E): the answer itself can be huge. If every node points to every later node, there are 2^n-2 paths (we ran it for n = 4, 6 and 10 and counted 4, 16 and 256), so the time grows with the total length of the output (plus any dead-end branches the search explores), and you should say that in an interview. If the graph can have cycles, the current path has to be tracked as a set so that a path does not revisit its own nodes.

A shortcut worth knowing: where must you start?

Suppose you may start from any nodes you like in a directed acyclic graph, and want the fewest starting nodes from which every node is reachable. A node with no incoming edge cannot be reached from anywhere, so it has to be a start itself. Every other node has an incoming edge and, going backwards along incoming edges, the walk cannot go on for ever in an acyclic graph, so it ends at a node without incoming edges: the nodes you already chose. So the answer is exactly the nodes with in-degree zero. No traversal is needed.

function findSmallestSetOfVertices(n, edges) {
  const hasIncoming = new Array(n).fill(false);
  for (const [, to] of edges) hasIncoming[to] = true;
  const result = [];
  for (let i = 0; i < n; i++) if (!hasIncoming[i]) result.push(i);
  return result;
}

O(V + E) time. The argument leans on the graph being acyclic. In a graph that has a cycle, a group of nodes can feed each other and still have no outside edge into it, and the in-degree test would miss it. We checked the function on random DAGs: its set reaches every node, and removing any node from the set leaves that node unreachable.

Weighted DFS: evaluate division

You get equations such as a / b = 2.0 and b / c = 3.0, and queries such as a / c. For each query, return the value, or -1 if it cannot be worked out. The trick is to see the variables as nodes and each equation as a weighted edge. a / b = 2 is an edge from a to b with weight 2, and it also tells you b / a = 1 / 2, so it is an edge back with weight 0.5, a directed pair for every equation. A query x / y asks for the product of the weights along a path from x to y, because x / y = (x / m) · (m / y) for any variable m in between. The chain a / b · b / c cancels the b and leaves a / c.

That is a graph search that carries a number along. Instead of the visited stack of plain nodes, push [node, product so far], where the product so far is start / node. When the search arrives at the target, the product is the answer.

function calcEquation(equations, values, queries) {
  const graph = new Map();
  const link = (a, b, ratio) => {
    if (!graph.has(a)) graph.set(a, []);
    graph.get(a).push([b, ratio]);
  };
  equations.forEach(([a, b], i) => {
    link(a, b, values[i]); // a / b = value
    link(b, a, 1 / values[i]); // so b / a = 1 / value
  });

  const evaluate = (from, to) => {
    if (!graph.has(from) || !graph.has(to)) return -1; // an unknown variable
    const seen = new Set([from]);
    const stack = [[from, 1]]; // [variable, from / variable]
    while (stack.length > 0) {
      const [node, product] = stack.pop();
      if (node === to) return product;
      for (const [next, ratio] of graph.get(node)) {
        if (!seen.has(next)) {
          seen.add(next);
          stack.push([next, product * ratio]); // from/next = (from/node) * (node/next)
        }
      }
    }
    return -1; // no chain of equations links them
  };

  return queries.map(([from, to]) => evaluate(from, to));
}

Dry run: a / b = 2, b / c = 3, then six queries

We ran the function and got exactly the answers above, and compared it with the true ratios on thousands of random consistent systems. Cost: one traversal per query, O(V + E) each, so O(Q · (V + E)) for Q queries. If there are many queries, a weighted union-find that stores each node's ratio to its root answers each one in near-constant time after the equations are merged; that version is in Union-find.

Clone graph, with a queue

The copy-with-a-map solution to clone graph is in Graphs: representation and traversal, written as recursion. Here is the same idea as BFS, which is the right choice when the graph can be deep, since a queue has no call-stack limit. The shape is a traversal where, on first sight of a neighbour, you also create and register its copy, and for every neighbour edge you link the copies. It uses GraphNode from that chapter.

function cloneGraphBfs(node) {
  if (node === null) return null;
  const copies = new Map([[node, new GraphNode(node.val)]]);
  const queue = [node];
  for (let head = 0; head < queue.length; head++) {
    const original = queue[head];
    for (const neighbor of original.neighbors) {
      if (!copies.has(neighbor)) {
        copies.set(neighbor, new GraphNode(neighbor.val)); // create and register on first sight
        queue.push(neighbor);
      }
      copies.get(original).neighbors.push(copies.get(neighbor));
    }
  }
  return copies.get(node);
}

The line that links the two copies sits outside the if, because an edge to an already-seen neighbour still has to be copied; only the creation of the copy happens once. Each node is created once and each edge is copied from both ends, so it is O(V + E) with O(V) space. This was checked on thousands of random graphs, with self-loops: the copy had the same shape and shared no node object with the original. The reverse mistake is to link the copies only when the neighbour is new, which loses every edge that leads back to a node already discovered.

Grids, word ladder and other state-space searches

Several of the best-known "graph" problems do not appear on this page, on purpose. Number of islands and its relatives, the multi-source spread of rotting oranges, the shortest path in a binary matrix, and the "which cells can reach both oceans" problem (reach from the border instead of towards it) all run on a grid where the neighbours are computed rather than stored. Word ladder, and the other problems where the nodes are states such as a word or a lock combination and the edges are one legal move, share the same shape. They are all one idea, BFS over an implicit graph, and they live in BFS on grids and implicit graphs. The components, cycles, colouring, trees and reachability on this page work on graphs you build from an edge list or a matrix, and they use the traversals from the previous chapter unchanged.

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
• "Is this a tree" / "is it connected with no cycle" → count the edges first (n - 1), then check connectivity
• "Can I reach everything / every room / which nodes must be starts" → one traversal and a look at the visited set, or the in-degrees for a DAG
• "List every path" → DFS that adds a node before the call and removes it after, copying the path when it ends
• Ratios, exchange rates, "A relates to B by a factor" → weighted edges in both directions and a product along the path
• Edges arriving one at a time with "are they connected yet" → union-find instead of a fresh traversal
• Grids, word ladder and other implicit graphs → BFS on grids and implicit graphs
• All of these reuse the exact same BFS/DFS skeleton from the previous chapter — the only new part is what you track while visiting