Advanced graphs: SCC, bridges, Euler paths, LCA

One DFS, two clocks: questions about structure

The graph chapters so far asked about paths: is there one, how short, in what order. This chapter asks about structure. Which vertices of a directed graph can all reach one another? Which single cable, or single server, splits a network when it fails? Can you walk along every edge exactly once? In a tree, who is the lowest common ancestor of two nodes, and which two nodes are farthest apart?

Each has an obvious brute force that deletes something and asks again: remove each edge and recount the pieces, or search from every vertex and compare what each can reach. That costs O(E · (V + E)) or O(V · (V + E)), fine for ten vertices and hopeless for a hundred thousand. The efficient answers come from one place: a single depth-first search that stamps every vertex with the moment it was first reached, and some reasoning about what the stamps say.

This chapter builds on Topological patterns and Advanced graph algorithms. Everything here is plain DFS with extra bookkeeping, so the work is in the reasoning.

The DFS tree and what each kind of edge tells you

Run a DFS and keep a counter. The first time you reach a vertex, give it the next number: its discovery time, tin[v]. The edges that lead to a vertex you have not seen are tree edges, and together they form the DFS tree (a forest, if the graph is not connected). Every other edge points, when you examine it, at a vertex that already has a tin. What that vertex is, relative to where you stand, is what this chapter is built on.

The last cell needs a proof, because bridges and articulation points rest on it. Say an undirected edge joins u and v, and the DFS reaches u first. Before u finishes it examines every edge it has, including u–v. Either v is still unvisited and the edge becomes a tree edge, or v was reached meanwhile through another child of u. Either way v is in u's subtree. So in an undirected DFS every non-tree edge joins a vertex to one of its ancestors, and nothing connects two branches except through their common ancestor. The whole bridge section is a consequence of that sentence.

This chapter uses two stamps: the discovery time tin, and the finish order (the order in which DFS calls return), which Kosaraju's algorithm uses. A derived number, low, built from tin, drives Tarjan's algorithm and the bridge algorithm.

Strongly connected components: what the problem asks

In a directed graph, say u and v belong together if u reaches v and v reaches u. The relation is reflexive, symmetric by definition and transitive (chain the walks), so it splits the vertices into groups with nothing left over. Each group is a strongly connected component, SCC for short. A vertex on no cycle is a component of its own, and so is one whose only cycle is a self-loop.

Think of modules that import each other, tasks that wait on one another (a deadlock is a component of more than one task), or pages you can click between in both directions. The brute force finds what every vertex reaches and pairs up those that reach each other: O(V · (V + E)). Both algorithms below take O(V + E).

The figure shows the fact that makes components useful. Collapse every component into one vertex and what is left has no cycle. A cycle through two components would let every vertex of one reach every vertex of the other and back, so they would be one component. This acyclic summary is the condensation.

Kosaraju: finish times and the reversed graph

Suppose someone hands you a vertex in a sink component, one with no edges leaving it. A DFS from there cannot escape and reaches the whole component, so the visited set is exactly that component. Mark it, remove it, repeat. The trouble is knowing which vertices sit in a sink.

Reverse every edge: the components stay the same, but sources and sinks swap. So find a vertex in a source component of the original graph and run the DFS on the reversed graph, where that component is now a sink and the search cannot leak out. Finish times point out such a vertex.

Lemma. If an edge goes from component C to a different component C', the latest finish time in C is later than the latest in C'. If the DFS enters C first, at a vertex x, then all of C and C' are unvisited and reachable from x, so they all become descendants of x and finish before it does. If the DFS enters C' first, it can never reach C (the condensation has no cycle), so all of C' finishes before C is even started.

Consequence: the vertex that finishes last overall lies in a source component, because a component with an edge entering it would have a later finisher. Running the DFS on the reversed graph from that vertex yields exactly its component. Then take the latest-finishing vertex not yet labelled; by the same argument it lies in a source of what remains. So: one DFS recording finish order, then a second pass over the reversed graph in decreasing finish order.

function sccKosaraju(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const radj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    radj[v].push(u); // the same edge, reversed
  }

  const seen = new Array(n).fill(false);
  const next = new Array(n).fill(0); // next[u] = how many of u's edges are already handled
  const finish = []; // vertices in the order their DFS call returns
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    const stack = [s];
    while (stack.length) {
      const u = stack[stack.length - 1];
      if (next[u] < adj[u].length) {
        const v = adj[u][next[u]++];
        if (!seen[v]) {
          seen[v] = true;
          stack.push(v);
        }
      } else {
        stack.pop();
        finish.push(u); // u is finished: everything it can reach is already seen
      }
    }
  }

  const comp = new Array(n).fill(-1);
  let count = 0;
  for (let i = n - 1; i >= 0; i--) { // latest finisher first
    const s = finish[i];
    if (comp[s] !== -1) continue;
    comp[s] = count;
    const stack = [s];
    while (stack.length) {
      const u = stack.pop();
      for (const v of radj[u]) {
        if (comp[v] === -1) { // reversed graph; labelled vertices are walls
          comp[v] = count;
          stack.push(v);
        }
      }
    }
    count++;
  }
  return { comp, count }; // comp[v] numbers follow a topological order of the components
}

Time O(V + E) and space O(V + E): two traversals and a reversed copy of the adjacency lists. Both use an explicit stack with an edge pointer, so no recursion depth is involved. The labels come out in topological order of the condensation: for every edge u → v, comp[u] <= comp[v]. I checked that on thousands of random graphs, along with the components themselves.

Dry run: the graph from the figure

Edges in input order: 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 1→6, 6→7, 7→6, 7→5. The first pass starts at 0 and takes edges in that order, so the vertices finish in the order 5, 4, 3, 2, 7, 6, 1, 0. The second pass reads that list from the right, walking reversed edges:

The third column is the point of the algorithm. Each blocked edge is a dashed edge of the figure, and because components are found source-first, every such edge meets a vertex that is already labelled.

Tarjan: deriving the low-link value

Kosaraju needs a reversed copy of the graph. Tarjan's algorithm finds the same components in one DFS, by noticing the moment a component is complete. Call the first vertex of a component that the DFS reaches its root r. Every other vertex of the component is reachable from r through unvisited vertices of the same component, so the DFS visits all of them before r returns: a component lives entirely inside the subtree of its root.

Keep a stack of visited vertices, pushing each one on discovery. When a root r finishes, everything above it on the stack was discovered later, so it lies in r's subtree. Could such a vertex w belong to another component with root r'? If r' is inside r's subtree, it has finished and that component has already been removed. If r' is above r, then r' reaches r down the tree, r reaches w, and w reaches r', which would put r in that component too. So the vertices above a finishing root are exactly its component: pop down to the root and you have emitted it. A vertex stays on the stack exactly while its root is still open.

One job is left: recognise a root when it finishes. Define

low[u] = the smallest tin you can reach from u by going down tree edges inside u's subtree and then taking at most one edge to a vertex that is on the stack.

The edge rule first. Take an edge x → v to an already visited v. If v is on the stack, its root rv is still open, so it is an ancestor of x, and x → v → rv → x is a cycle: v is in x's component. If v is not on the stack, its component was emitted already, and x, which is still open, is not in it; x reaches v, so v cannot reach x, and the edge tells you nothing about x's component. The test onStack[v] is not an optimisation. It separates these two cases.

Now u is a root exactly when low[u] == tin[u]. Suppose u is a root but some edge from its subtree, from x, reached a stack vertex v with tin[v] < tin[u]. The root of x's component is open, so it is an ancestor of x with tin at most tin[v], hence a proper ancestor of u. It reaches u down the tree, u reaches x, and x reaches it: then u is not a root after all. Conversely, if u is not a root, its component has a path from u to its root, an ancestor. Follow the path until it first leaves u's subtree. That edge goes to a vertex discovered before u (a later one would have become a descendant), and the vertex is in the component, so on the stack. It pulls low[u] below tin[u]. And after a child v returns, low[u] = min(low[u], low[v]), because whatever the child's subtree can reach, u can reach through the tree edge.

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

  const tin = new Array(n).fill(-1); // discovery time; -1 means unvisited
  const low = new Array(n).fill(0); // smallest tin reachable, see the derivation
  const onStack = new Array(n).fill(false);
  const open = []; // visited vertices whose component is not closed yet
  const comp = new Array(n).fill(-1);
  let timer = 0;
  let count = 0;

  function dfs(u) {
    tin[u] = low[u] = timer++;
    open.push(u);
    onStack[u] = true;

    for (const v of adj[u]) {
      if (tin[v] === -1) {
        dfs(v);
        low[u] = Math.min(low[u], low[v]); // whatever v's subtree can reach, u can reach
      } else if (onStack[v]) {
        low[u] = Math.min(low[u], tin[v]); // an edge into a still-open component
      }
    }

    if (low[u] === tin[u]) { // u reaches nothing earlier: u is the root of its component
      let w;
      do {
        w = open.pop();
        onStack[w] = false;
        comp[w] = count;
      } while (w !== u);
      count++;
    }
  }

  for (let s = 0; s < n; s++) if (tin[s] === -1) dfs(s);
  return { comp, count }; // components are numbered in reverse topological order
}

Each vertex is pushed and popped once and each edge examined once: O(V + E) time, O(V) extra space beyond the adjacency lists. Components come out sinks first: for every edge u → v, comp[u] >= comp[v], the opposite numbering from Kosaraju. That matters for the DP in the next section.

Dry run: the same graph, edges in the same order

The row for edge 7→5 is the one to remember. Without the onStack test, low[7] would become 5, vertex 6 would no longer look like a root, and {6, 7} would be absorbed into the component of 0, 1, 2. I ran that variant: it reports two components instead of three.

Either is accepted in an interview. Kosaraju is easier to explain from scratch; Tarjan is one pass, and its low-link idea also solves bridges, so it pays twice. Pick the one you can reproduce under pressure.

Condensation: collapse each component into one vertex

Once every vertex has a component label, build the condensation: one vertex per component, and an edge between two components if any original edge goes from one to the other. As shown above it is a DAG, so everything from Topological patterns applies to it.

function condense(n, edges, comp, count) {
  const seen = Array.from({ length: count }, () => new Set());
  const dag = Array.from({ length: count }, () => []);
  const indeg = new Array(count).fill(0);
  const outdeg = new Array(count).fill(0);
  for (const [u, v] of edges) {
    const a = comp[u];
    const b = comp[v];
    if (a === b || seen[a].has(b)) continue; // edges inside a component vanish, parallel ones merge
    seen[a].add(b);
    dag[a].push(b);
    outdeg[a]++;
    indeg[b]++;
  }
  return { dag, indeg, outdeg };
}

function edgesToMakeStronglyConnected(n, edges) {
  const { comp, count } = sccTarjan(n, edges);
  if (count === 1) return 0;
  const { indeg, outdeg } = condense(n, edges, comp, count);
  const sources = indeg.filter((d) => d === 0).length;
  const sinks = outdeg.filter((d) => d === 0).length;
  return Math.max(sources, sinks); // each new edge can cure one source and one sink at most
}

Edges inside a component disappear, and parallel edges between two components are kept once, using a Set. The degree arrays answer two classic questions.

• Fewest starting vertices that reach everything. Every source component (in-degree 0) needs a start of its own, since nothing outside can enter it. One start per source is enough: following edges backwards from any component must stop (the graph is acyclic), and it stops at a source. The answer is the number of source components.
• Fewest edges to add to make the graph strongly connected. With one component, 0. Otherwise each source needs a new edge entering it and each sink a new edge leaving it, and one new edge repairs at most one of each, so at least max(sources, sinks) edges are needed. That many also suffice (a classical result). I checked the formula against a brute force that tries every set of added edges, on random graphs of up to five vertices.

The other use is a DP over the condensation. Say every city has a value, you may walk along roads and revisit cities, and each city's value counts once. Inside a component you can reach every city, so a component counts as a whole; across components the graph is a DAG, so a longest-path DP applies. Tarjan's numbering suits it: successors of a component have smaller ids, so going through ids from 0 upward finishes every successor first.

function maxValueOnWalk(n, edges, value) {
  const { comp, count } = sccTarjan(n, edges);
  const total = new Array(count).fill(0);
  for (let v = 0; v < n; v++) total[comp[v]] += value[v]; // a component is visited as a whole, once
  const { dag } = condense(n, edges, comp, count);

  const best = new Array(count).fill(0);
  for (let c = 0; c < count; c++) { // Tarjan numbers sinks first: every successor of c has a smaller id
    let after = 0;
    for (const d of dag[c]) after = Math.max(after, best[d]);
    best[c] = total[c] + after;
  }
  return Math.max(0, ...best);
}

The values must be non-negative for "take the whole component" to be right. SCCs appear in one more classic place, 2-SAT: one vertex per literal, two edges per clause, and the formula is unsatisfiable exactly when some variable and its negation share a component.

Bridges and articulation points

A bridge is an edge whose removal disconnects its part of an undirected graph; an articulation point (cut vertex) is a vertex whose removal does. They are the single points of failure of a network, and "Critical Connections in a Network" asks for the bridges directly. The brute force removes each edge and counts the pieces: O(E · (V + E)).

Use the fact proved earlier: in an undirected DFS every non-tree edge goes to an ancestor. Look at a tree edge u–v, v the child. Cut it, and the subtree of v stays attached to the rest only through non-tree edges that leave the subtree. Those can only go up to an ancestor of v, that is, to u or to something above it, and a single such edge is enough. So the edge u–v is a bridge exactly when no edge from v's subtree reaches u or anything above it.

To test that cheaply, let low[v] be the smallest tin among v itself and the far ends of all back edges leaving v's subtree. It is computed bottom-up, as the minimum over v's own back edges and its children's low: the update of Tarjan's algorithm, minus the stack, since in an undirected graph a visited neighbour is always an ancestor or a descendant and "is it still open?" never arises. The test is low[v] > tin[u].

function findBridges(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b], id) => {
    adj[a].push([b, id]); // remember WHICH edge, not just which neighbour
    adj[b].push([a, id]);
  });

  const tin = new Array(n).fill(-1);
  const low = new Array(n).fill(0);
  const bridges = [];
  let timer = 0;

  function dfs(u, parentEdge) {
    tin[u] = low[u] = timer++;
    for (const [v, id] of adj[u]) {
      if (id === parentEdge) continue; // do not walk back along the edge we arrived by
      if (tin[v] !== -1) {
        low[u] = Math.min(low[u], tin[v]); // a back edge to an earlier vertex
      } else {
        dfs(v, id);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > tin[u]) bridges.push([u, v]); // v's subtree cannot get above u: edge u-v is a bridge
      }
    }
  }

  for (let s = 0; s < n; s++) if (tin[s] === -1) dfs(s, -1);
  return bridges;
}

Dry run: the graph from the figure, starting at vertex 0

Each non-tree edge is examined from both ends, harmlessly. From vertex 3, the edge to its descendant 5 reaches a vertex with tin 5, larger than tin[3], so min(low[3], 5) changes nothing. Only the lower end of a back edge can learn anything.

Articulation points use the same numbers, with one change and one special case. Remove the vertex u itself. A child's subtree is cut off unless a back edge from it reaches a proper ancestor of u; an edge that lands on u no longer helps, since u is gone. So a non-root u is a cut vertex when some child has low[v] >= tin[u]: >=, not >. In the dry run low[4] = 3 = tin[3], so vertex 3 is a cut vertex, although edge 3–4 is not a bridge.

The root needs its own rule. It has the smallest tin, so every child satisfies low[v] >= tin[root] trivially, and the general test would flag any root that has a child. But a root with one child is not a cut vertex: everything else hangs below that child and stays connected without the root. Since no edge joins two branches, the root's subtrees are linked to each other only through it, so the root is a cut vertex exactly when it has two or more tree children.

function findCutVertices(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b], id) => {
    adj[a].push([b, id]);
    adj[b].push([a, id]);
  });

  const tin = new Array(n).fill(-1);
  const low = new Array(n).fill(0);
  const isCut = new Array(n).fill(false);
  let timer = 0;

  function dfs(u, parentEdge) {
    tin[u] = low[u] = timer++;
    let children = 0; // tree children of u
    for (const [v, id] of adj[u]) {
      if (id === parentEdge) continue;
      if (tin[v] !== -1) {
        low[u] = Math.min(low[u], tin[v]);
      } else {
        children++;
        dfs(v, id);
        low[u] = Math.min(low[u], low[v]);
        if (parentEdge !== -1 && low[v] >= tin[u]) isCut[u] = true; // non-root: ">=", not ">"
      }
    }
    if (parentEdge === -1 && children >= 2) isCut[u] = true; // the root has its own rule
  }

  for (let s = 0; s < n; s++) if (tin[s] === -1) dfs(s, -1);
  return isCut.flatMap((flag, v) => (flag ? [v] : []));
}

Delete the bridges and the connected pieces that remain are the 2-edge-connected components, groups where any single cable can fail without splitting the group; the bridges form a tree over them, the same trick as the condensation for directed graphs.

Euler paths and circuits: use every edge once

An Euler path walks along every edge exactly once; an Euler circuit does so and ends where it began. The question is about edges, not vertices, and that makes it easy: a clean test and a linear-time construction. (Visiting every vertex once is the Hamiltonian problem, which has no known fast algorithm.)

The test comes from counting. Each time a walk passes through a vertex it uses one edge to arrive and another to leave. So for every vertex that is neither the start nor the end, the edges at it pair up.

A self-loop adds 2 to a vertex's degree, so it never changes parity. The conditions are necessary by the pairing argument; sufficiency is exactly what the construction below proves. Here is the undirected test:

function eulerKind(n, edges) {
  const degree = new Array(n).fill(0);
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    degree[a]++;
    degree[b]++; // a self-loop [a, a] adds 2 to a, which keeps the parity right
    adj[a].push(b);
    adj[b].push(a);
  }

  const start = degree.findIndex((d) => d > 0);
  if (start === -1) return "circuit"; // no edges: the empty walk uses them all
  const seen = new Array(n).fill(false);
  seen[start] = true;
  const stack = [start];
  while (stack.length) {
    const u = stack.pop();
    for (const v of adj[u]) {
      if (!seen[v]) {
        seen[v] = true;
        stack.push(v);
      }
    }
  }
  for (let v = 0; v < n; v++) if (degree[v] > 0 && !seen[v]) return "none"; // edges in two separate pieces

  const odd = degree.filter((d) => d % 2 === 1).length;
  if (odd === 0) return "circuit";
  if (odd === 2) return "path";
  return "none";
}

The connectivity loop is not decoration. Two separate triangles have every degree even, and no walk can use edges of both.

Hierholzer: building the walk

Start at the right vertex (the one with the surplus out-edge for a directed path, an odd vertex for an undirected one, anything for a circuit) and keep walking along unused edges. Because of the degree conditions you can only get stuck at the end of the trail: every other vertex you enter has a spare edge to leave by. But that walk may not use all the edges. The unused ones are balanced (each vertex has as many unused edges in as out, or an even number), so from any vertex of the walk that still has unused edges you can start a new walk, and it can only get stuck back where it began, closing a loop. Splice the loop in at that vertex and continue.

The stack does this automatically. Push the start. While the stack is not empty, look at the top vertex u: if it has an unused edge, take it and push the new vertex; otherwise u is stuck, so pop it and write it to the output. A vertex is written only when nothing is left to do after it, so the output is the trail backwards; reverse it at the end. A detour is written before the vertex it started from, and after the reversal it sits between that vertex's arrival and its departure: that is the splice.

function eulerPathDirected(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const balance = new Array(n).fill(0); // out-degree minus in-degree
  for (const [u, v] of edges) {
    adj[u].push(v);
    balance[u]++;
    balance[v]--;
  }

  let start = -1;
  let ends = 0;
  for (let v = 0; v < n; v++) {
    if (balance[v] === 1) {
      if (start !== -1) return null; // two vertices want to be the start
      start = v;
    } else if (balance[v] === -1) {
      ends++;
    } else if (balance[v] !== 0) {
      return null;
    }
  }
  if (ends > 1) return null;
  if (start === -1) start = edges.length ? edges[0][0] : 0; // balanced: a circuit, any vertex with an edge will do

  const next = new Array(n).fill(0); // next unused edge of each vertex
  const stack = [start];
  const path = [];
  while (stack.length) {
    const u = stack[stack.length - 1];
    if (next[u] < adj[u].length) {
      stack.push(adj[u][next[u]++]); // use one more edge and walk along it
    } else {
      path.push(stack.pop()); // stuck: u is the last vertex of what is still unwritten
    }
  }

  if (path.length !== edges.length + 1) return null; // some edges were unreachable from start
  return path.reverse();
}

Each edge is consumed once through the next pointer, so the time is O(V + E). The final length check doubles as the connectivity test: if fewer than edges.length + 1 vertices were written, some edges lay in a piece that start cannot reach. The undirected version needs one extra detail: every edge is in two adjacency lists, so a used[id] flag marks it gone from both ends.

function eulerTrailUndirected(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b], id) => {
    adj[a].push([b, id]);
    adj[b].push([a, id]);
  });

  const odd = [];
  for (let v = 0; v < n; v++) if (adj[v].length % 2 === 1) odd.push(v);
  if (odd.length !== 0 && odd.length !== 2) return null;

  let start = odd.length ? odd[0] : adj.findIndex((list) => list.length > 0);
  if (start === -1) start = 0; // no edges at all

  const used = new Array(edges.length).fill(false); // an undirected edge is listed twice: mark it once
  const next = new Array(n).fill(0);
  const stack = [start];
  const path = [];
  while (stack.length) {
    const u = stack[stack.length - 1];
    while (next[u] < adj[u].length && used[adj[u][next[u]][1]]) next[u]++; // skip edges used from the other end
    if (next[u] < adj[u].length) {
      const [v, id] = adj[u][next[u]++];
      used[id] = true;
      stack.push(v);
    } else {
      path.push(stack.pop());
    }
  }

  if (path.length !== edges.length + 1) return null;
  return path.reverse();
}

Both functions were compared with a brute force that tries every ordering of the edges, on thousands of random multigraphs with self-loops and parallel edges: they agree on whether a trail exists, and every trail they return is checked to use each edge exactly once.

Reconstruct Itinerary: Hierholzer with lexical order

"Reconstruct Itinerary" gives you a list of tickets [from, to]. Start at "JFK", use every ticket exactly once, and return the itinerary that is smallest in lexical order. A valid itinerary is promised to exist, so this is an Euler path in a directed multigraph, with one twist: among all of them you must produce the lexically smallest.

The obvious greedy approach, always taking the smallest available destination, fails. With tickets JFK→KUL, JFK→NRT, NRT→JFK, the smallest choice from JFK is KUL, which has no ticket out: the walk is stuck with two tickets unused. Hierholzer repairs this in one pass. A trap is a vertex where the walk gets stuck, and the algorithm writes the stuck vertex first, so after the reversal it lands last: the ticket into the trap becomes the final departure from JFK, where it has to be.

So taking the smallest unused ticket first gives the lexically smallest itinerary: a smallest ticket that is a trap is moved to last, and any other smallest ticket is used first, which is as small as it can be. I checked this against a brute force that enumerates every valid itinerary of random ticket sets and keeps the minimum (over twenty thousand cases with an answer).

function findItinerary(tickets) {
  const adj = new Map();
  for (const [from, to] of tickets) {
    if (!adj.has(from)) adj.set(from, []);
    adj.get(from).push(to);
  }
  for (const list of adj.values()) list.sort().reverse(); // smallest destination at the END, so pop() is O(1)

  const stack = ["JFK"];
  const route = [];
  while (stack.length) {
    const airport = stack[stack.length - 1];
    const options = adj.get(airport);
    if (options && options.length) {
      stack.push(options.pop()); // the smallest unused ticket out of here
    } else {
      route.push(stack.pop()); // stuck: this airport comes last among those still unplaced
    }
  }
  return route.reverse();
}

Dry run: JFK→KUL, JFK→NRT, NRT→JFK

After sorting, JFK has [NRT, KUL] with the smallest, KUL, at the end, and NRT has [JFK].

Reversed, the route is JFK, NRT, JFK, KUL: the greedy first choice, KUL, was not discarded, only moved to the end. The code returns this itinerary.

Time: O(E log E) for the sorting of the adjacency lists, O(E) for the walk. A variant, "Valid Arrangement of Pairs", has integer vertices and asks for any ordering of the pairs so that each pair starts where the previous one ended: the same algorithm, with the start chosen by the out − in = 1 rule.

Binary lifting: LCA and the kth ancestor

You are given a tree as a parent array (parent[root] = -1) and many queries: the kth ancestor of v, or the lowest common ancestor of u and v. Walking up one parent at a time costs O(depth) per query, which is O(n) on a path-shaped tree; with n and the number of queries both near 10⁵ that is about 10¹⁰ steps.

Precompute, for every vertex, its 1st, 2nd, 4th, 8th... ancestor, and call the 2^jth one up[j][v]. Each row comes from the one before, because 2^j steps are two jumps of 2^j−1 steps: up[j][v] = up[j−1][ up[j−1][v] ]. Any k is a sum of distinct powers of two, its binary digits, so the kth ancestor is reached by taking up[j] for every set bit j of k: at most log₂ n jumps. The table has n · ⌈log₂ n⌉ entries.

For the LCA, lift the deeper vertex by the depth difference so both are on the same level. If they coincide, that is the answer. Otherwise go through the jumps from the longest to the shortest, and whenever the two 2^jth ancestors differ, take that jump with both. This works because "the 2^jth ancestors are the same vertex" is monotone in j: once a jump is long enough to reach a common ancestor, every longer one does too. The loop is a binary search for the longest jump that stays below the LCA, and afterwards both vertices are children of the LCA.

function buildLifting(parent) {
  const n = parent.length;
  let LOG = 1;
  while (1 << LOG < n) LOG++; // smallest LOG with 2^LOG >= n; integer arithmetic, no Math.log2

  const up = [parent.slice()]; // up[0][v] = parent of v, or -1 above the root
  for (let j = 1; j < LOG; j++) {
    const prev = up[j - 1];
    up.push(prev.map((mid) => (mid === -1 ? -1 : prev[mid]))); // 2^j steps = 2^(j-1) steps, twice
  }

  const children = Array.from({ length: n }, () => []);
  const queue = [];
  for (let v = 0; v < n; v++) {
    if (parent[v] === -1) queue.push(v);
    else children[parent[v]].push(v);
  }
  const depth = new Array(n).fill(0);
  for (let head = 0; head < queue.length; head++) { // breadth-first from the root: no recursion
    const u = queue[head];
    for (const c of children[u]) {
      depth[c] = depth[u] + 1;
      queue.push(c);
    }
  }
  return { up, depth, LOG, n };
}

function kthAncestor(lift, v, k) {
  if (k >= lift.n) return -1; // no vertex is that deep, and the bits of k would run off the table
  for (let j = 0; k > 0 && v !== -1; j++, k >>= 1) {
    if (k & 1) v = lift.up[j][v]; // take the 2^j jump when bit j of k is set
  }
  return v;
}

function lca(lift, u, v) {
  if (lift.depth[u] < lift.depth[v]) [u, v] = [v, u]; // make u the deeper one
  u = kthAncestor(lift, u, lift.depth[u] - lift.depth[v]); // bring both to the same depth
  if (u === v) return u;
  for (let j = lift.LOG - 1; j >= 0; j--) {
    if (lift.up[j][u] !== lift.up[j][v]) { // the jump lands on different vertices: it stays below the LCA
      u = lift.up[j][u];
      v = lift.up[j][v];
    }
  }
  return lift.up[0][u]; // one step above both is the LCA (-1 if they sit in different trees)
}

Dry run: a ten-vertex tree

parent = [-1, 0, 0, 1, 1, 2, 3, 3, 4, 7], so 0 is the root, 1 and 2 are its children, 3 and 4 are children of 1, and 9 hangs below 7, below 3. The depths are 0, 1, 1, 2, 2, 2, 3, 3, 3, 4. Here LOG is 4.

kthAncestor(9, 3): 3 is binary 11, so take up[0] then up[1]: 9 → 7 → 1. kthAncestor(9, 5) is −1, since 9 has depth 4 and only four ancestors. lca(9, 8): depth(9) = 4, depth(8) = 3, so lift 9 by one to get 7. Since 7 ≠ 8, scan the jumps from the top: j = 3 and j = 2 give −1 for both, equal, skip; j = 1 gives 1 for both, equal, skip; j = 0 gives 3 and 4, different, so move to u = 3 and v = 4. The answer is up[0][3] = 1. Check on the tree: 9's path goes 9, 7, 3, 1, 0 and 8's goes 8, 4, 1, 0, so 1 is their lowest common ancestor.

Costs: O(n log n) time and space to build, O(log n) per query. The table can carry extra data per jump, such as the maximum edge weight on the way up, to answer path queries; and because a new leaf's rows depend only on rows that already exist, a leaf can be added in O(log n), which is the setting of "Kth Ancestor of a Tree Node". If all queries are known in advance, offline Tarjan LCA with Union-Find, or an Euler tour with a sparse table for O(1) per query, are alternatives. For one query on a binary tree, plain recursion is simpler.

Tree diameter: two sweeps and a DP

The diameter of a tree is the length of the longest path between any two vertices, counted in edges, or as the sum of edge weights when edges have weights. The brute force runs a traversal from every vertex: O(n²). There are two linear methods.

Method 1, two sweeps. Start anywhere and find the vertex a farthest from it; then find the vertex b farthest from a. The distance from a to b is the diameter. The claim to prove is that the first farthest vertex ends some longest path. Take a longest path P with ends x and y, a start s and a farthest vertex f. Let p and q be the vertices of P closest to s and to f.

If p ≠ q, say q is on the y side. The paths s → f and s → y both run through p and q, and f being at least as far as y gives d(q, f) ≥ d(q, y). Then d(f, x) = d(f, q) + d(q, p) + d(p, x) ≥ d(y, q) + d(q, p) + d(p, x) = d(x, y). If p = q, the path s → x goes through p, and d(s, f) ≥ d(s, x) with d(s, f) ≤ d(s, p) + d(p, f) gives d(p, f) ≥ d(p, x), and likewise for y; so d(f, y) = d(f, p) + d(p, y) ≥ d(x, p) + d(p, y) = d(x, y). Either way f ends a longest path, so the second sweep starts from such an end and its farthest vertex is at distance exactly the diameter. The argument needs only non-negative distances.

function farthest(adj, start) {
  const dist = new Map([[start, 0]]);
  const stack = [start];
  let best = start;
  while (stack.length) {
    const u = stack.pop();
    if (dist.get(u) > dist.get(best)) best = u;
    for (const [v, w] of adj[u]) {
      if (!dist.has(v)) { // in a tree, "not seen yet" means "not the vertex I came from"
        dist.set(v, dist.get(u) + w);
        stack.push(v);
      }
    }
  }
  return [best, dist.get(best)];
}

function treeDiameterTwoSweeps(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w = 1] of edges) {
    adj[u].push([v, w]);
    adj[v].push([u, w]);
  }
  const [a] = farthest(adj, 0); // sweep 1: any start, find the farthest vertex
  const [b, length] = farthest(adj, a); // sweep 2: from that vertex, the farthest one is the other end
  return { length, ends: [a, b] };
}

Method 2, DP over children. For each vertex, let top1 be the longest downward path from it and top2 the longest one through a different child. The longest path that has this vertex as its highest point is top1 + top2, and the diameter is the best of those over all vertices. Processing vertices in reverse breadth-first order guarantees that children are done before their parent, with no recursion.

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

  const parent = new Array(n).fill(-1);
  const parentWeight = new Array(n).fill(0);
  const seen = new Array(n).fill(false);
  const order = [0]; // breadth-first order: every parent before its children
  seen[0] = true;
  for (let head = 0; head < order.length; head++) {
    const u = order[head];
    for (const [v, w] of adj[u]) {
      if (!seen[v]) {
        seen[v] = true;
        parent[v] = u;
        parentWeight[v] = w;
        order.push(v);
      }
    }
  }

  const top1 = new Array(n).fill(0); // longest downward path from each vertex
  const top2 = new Array(n).fill(0); // second longest, through a different child
  let best = 0;
  for (let i = order.length - 1; i >= 0; i--) { // children before parents
    const u = order[i];
    best = Math.max(best, top1[u] + top2[u]); // the best path that bends at u
    const p = parent[u];
    if (p === -1) continue;
    const reach = top1[u] + parentWeight[u];
    if (reach > top1[p]) {
      top2[p] = top1[p];
      top1[p] = reach;
    } else if (reach > top2[p]) {
      top2[p] = reach;
    }
  }
  return best;
}

Dry run: a weighted tree

Edges (u, v, weight): (0,1,2), (1,2,3), (1,3,1), (0,4,4), (4,5,2), (5,6,5), (4,7,1).

The diameter is 16: the path 6, 5, 4, 0, 1, 2 with weights 5 + 2 + 4 + 2 + 3. The DP finds the same number:

A neighbour of this problem is "Minimum Height Trees": the roots that give the smallest height are the middle one or two vertices of a longest path. Find a diameter, and its midpoint is the answer.

Deep graphs: the recursion limit and the explicit stack

A JavaScript engine gives the call stack a fixed budget. This measures it on your own machine:

function recursionDepth() {
  let depth = 0;
  function dive() {
    depth++;
    dive();
  }
  try {
    dive();
  } catch (error) {
    return depth; // a RangeError: Maximum call stack size exceeded
  }
}

On the Node 24 used to check this chapter, an empty recursive function reached roughly ten thousand frames. A real DFS frame holds arrays, a loop and an iterator, so it fares worse: a recursive Tarjan on a graph that is one long path overflowed at about 5,000 vertices, and the recursive bridge finder at about 4,400. The numbers depend on the engine and the frame size, so do not rely on them; the lesson is the order of magnitude. A path of 10⁵ vertices, a normal test when the statement says n ≤ 10⁵, crashes every recursive DFS here.

The fix is mechanical: keep the call stack in an array, and replace the for loop over neighbours with a per-vertex edge pointer.

sccTarjan earlier in the chapter is the recursive form of that table; applying the recipe to it line by line gives the iterative version the first practice exercise asks for. The next function does it for bridges and cut vertices in one pass. Kosaraju, Hierholzer, the diameter code and the lifting table were written without recursion from the start.

function bridgesAndCutVertices(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b], id) => {
    adj[a].push([b, id]);
    adj[b].push([a, id]);
  });

  const tin = new Array(n).fill(-1);
  const low = new Array(n).fill(0);
  const next = new Array(n).fill(0);
  const viaEdge = new Array(n).fill(-1); // the edge id each vertex was first reached by
  const isCut = new Array(n).fill(false);
  const bridges = [];
  let timer = 0;

  for (let root = 0; root < n; root++) {
    if (tin[root] !== -1) continue;
    tin[root] = low[root] = timer++;
    const calls = [root];
    let rootChildren = 0;

    while (calls.length) {
      const u = calls[calls.length - 1];
      if (next[u] < adj[u].length) {
        const [v, id] = adj[u][next[u]++];
        if (id === viaEdge[u]) continue;
        if (tin[v] !== -1) {
          low[u] = Math.min(low[u], tin[v]);
        } else {
          tin[v] = low[v] = timer++;
          viaEdge[v] = id;
          calls.push(v);
          if (u === root) rootChildren++;
        }
      } else {
        calls.pop(); // u is done; its parent p is the new top of the stack
        if (calls.length) {
          const p = calls[calls.length - 1];
          low[p] = Math.min(low[p], low[u]);
          if (low[u] > tin[p]) bridges.push([p, u]);
          if (p !== root && low[u] >= tin[p]) isCut[p] = true;
        }
      }
    }
    if (rootChildren >= 2) isCut[root] = true;
  }
  return { bridges, cutVertices: isCut.flatMap((flag, v) => (flag ? [v] : [])) };
}

Both iterative versions agree with the recursive ones on random graphs, and they ran in a fraction of a second on a path of 300,000 vertices, where the recursive versions throw. In an interview it is reasonable to write the recursive form first, name the depth risk, and offer the stack version when the constraints are large.

Recognizing it in an unseen problem

• Groups of things that can all reach each other, a cycle in a directed graph that must be reported as a whole, or "minimum starting points to reach everything": strongly connected components, then the condensation DAG.
• "Critical", "single point of failure", "removing this edge/server disconnects": bridges or articulation points with low-link.
• "Use every edge exactly once", "reconstruct the route from tickets", "order the dominoes/pairs so each starts where the last ended": Euler path; check degrees, then Hierholzer. If the statement says every vertex once, it is a different, much harder problem.
• "Lowest common ancestor" or "kth ancestor" with many queries on a large tree: binary lifting. One query, or a binary search tree: a simple walk is enough.
• "Longest path in a tree", "farthest two nodes", "worst-case distance": diameter by two sweeps or the DP. "Best root to minimise the height": the middle of the diameter.
• Watch the graph type. Bridges and articulation points are for undirected graphs; SCC is for directed graphs; the two sweeps are for trees. Check directed or undirected, connected or not, multi-edges or self-loops before choosing.
• Check the input size. If n reaches 10⁵ and the graph can be a long path, plan the explicit stack from the start.