0

Minimum starting vertices to reach a cyclic directed graph

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Minimum starting vertices to reach a cyclic directed graph

Companies: Airbnb

Difficulty: Hard

Problem statement

You are given a directed graph with n vertices labeled 0 to n - 1 and a list edges, where edges[i] = [u, v] is a directed edge from u to v. The graph may contain cycles, self-loops and duplicate edges.

Choose the smallest set of starting vertices such that every vertex in the graph can be reached from at least one of them (a starting vertex reaches itself).

Implement:

def min_start_vertices(n: int, edges: list[list[int]]) -> list[int]: ...

If several minimum sets exist, return the one that uses the smallest vertex id from each group of interchangeable choices, sorted in ascending order.

Constraints

  • 0 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • 0 <= u, v < n

Example 1

n = 5, edges = [[0, 1], [1, 2], [2, 0], [3, 2]]

Output: [3, 4]. Vertex 3 reaches the cycle 0 -> 1 -> 2 -> 0. Vertex 4 has no edges, so it must be chosen itself.

Example 2

n = 4, edges = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2]]

Output: [0]. Every vertex has an incoming edge, but starting at 0 reaches 1, then 2 and 3.

Note: if the graph had no cycles, the answer would simply be the vertices with no incoming edges. Your solution must handle cycles.

Approach

Clarify first. Ask these before coding:

  • Can the graph have cycles? Yes. This is what makes it harder than the DAG version (LeetCode 1557). Self-loops and duplicate edges can appear too.
  • What do we return? The list of starting vertices, not only the count. If several answers have the same size, return the one with the smallest id in each group, sorted ascending. That makes the output deterministic and easy to test.
  • Isolated vertices? A vertex with no edges must be started on its own.

Why "in-degree zero" is not enough. In a DAG, the answer is exactly the vertices with in-degree 0. Every other vertex has a parent, and following parents backwards must end at a root. With a cycle like 0 -> 1 -> 2 -> 0, every vertex has in-degree 1, so that rule returns nothing. We still need one start inside the cycle.

Brute force. Repeatedly pick a vertex, BFS from it, and mark everything reached. The order matters: starting at a vertex that some other unreached vertex can reach wastes a pick. Trying every order, or checking for every vertex whether it is reachable from some other start, costs O(V * (V + E)) or worse. Say it, then move on.

Optimal: condense strongly connected components (SCCs).

  1. Find the SCCs. Inside one SCC every vertex reaches every other, so one start inside it covers the whole component.
  2. Collapse each SCC to one node. The result is a DAG (the condensation).
  3. A component needs its own start exactly when no edge enters it from another component (its in-degree in the condensation is 0). Any other component is reached from some source component, by the DAG argument above.
  4. Pick one vertex from each source component. Use the smallest id for a stable answer.

Why it is minimal. No vertex outside a source component can reach into it, so every valid answer must contain at least one vertex from each source component. Picking exactly one from each already reaches everything. So the answer size equals the number of source components.

Finding SCCs. Use Kosaraju: one DFS on the graph records finish order, then a DFS on the reversed graph, in reverse finish order, labels one component per tree. Both DFS passes are iterative so a long chain of 10^5 vertices does not hit Python's recursion limit. Tarjan's algorithm works equally well with one pass; Kosaraju is easier to get right on a whiteboard.

Shortcut worth mentioning. After the first pass, walk vertices in decreasing finish time and run a forward DFS from each one not yet reached; each new root is one answer. The vertex with the largest remaining finish time is always in a source component of what is left. This gives a minimal set without building the condensation, but the chosen vertices are not the smallest ids.

Invariant. If there is an edge from component A to a different component B, the largest finish time in A is greater than the largest in B. This is why processing by decreasing finish time on the reversed graph peels off one SCC at a time.

Code

from __future__ import annotations


def min_start_vertices(n: int, edges: list[list[int]]) -> list[int]:
    """Smallest set of vertices from which every vertex is reachable.

    Returns the smallest vertex id of each source SCC, sorted ascending.
    """
    graph: list[list[int]] = [[] for _ in range(n)]
    reverse: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        reverse[v].append(u)

    # Pass 1: iterative DFS on the graph, record vertices by finish time.
    order: list[int] = []
    seen = [False] * n
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        stack: list[tuple[int, int]] = [(start, 0)]
        while stack:
            node, idx = stack[-1]
            if idx < len(graph[node]):
                stack[-1] = (node, idx + 1)
                nxt = graph[node][idx]
                if not seen[nxt]:
                    seen[nxt] = True
                    stack.append((nxt, 0))
            else:
                stack.pop()
                order.append(node)

    # Pass 2: DFS on the reversed graph in decreasing finish time.
    comp = [-1] * n
    count = 0
    for start in reversed(order):
        if comp[start] != -1:
            continue
        comp[start] = count
        todo = [start]
        while todo:
            node = todo.pop()
            for prev in reverse[node]:
                if comp[prev] == -1:
                    comp[prev] = count
                    todo.append(prev)
        count += 1

    # A component is a source if no edge enters it from another component.
    has_incoming = [False] * count
    for u, v in edges:
        if comp[u] != comp[v]:
            has_incoming[comp[v]] = True

    smallest = [n] * count
    for node in range(n):
        smallest[comp[node]] = min(smallest[comp[node]], node)

    return sorted(smallest[c] for c in range(count) if not has_incoming[c])


def min_start_count(n: int, edges: list[list[int]]) -> int:
    return len(min_start_vertices(n, edges))


if __name__ == "__main__":
    # DAG: matches the in-degree-zero answer.
    assert min_start_vertices(6, [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]]) == [0, 3]
    # One big cycle: every in-degree is 1, but one start is needed.
    assert min_start_vertices(3, [[0, 1], [1, 2], [2, 0]]) == [0]
    # Source cycle {2, 3} feeds a sink cycle {0, 1}.
    assert min_start_vertices(4, [[0, 1], [1, 0], [2, 3], [3, 2], [3, 0]]) == [2]
    # Isolated vertices and a self-loop.
    assert min_start_vertices(4, [[1, 1]]) == [0, 1, 2, 3]
    assert min_start_vertices(1, []) == [0]
    assert min_start_vertices(0, []) == []
    # Duplicate edges.
    assert min_start_vertices(3, [[0, 1], [0, 1], [1, 2]]) == [0]
    # Long chain: no recursion limit issues.
    big = 200_000
    assert min_start_vertices(big, [[i, i + 1] for i in range(big - 1)]) == [0]
    # Long cycle closing back to the start.
    assert min_start_count(big, [[i, (i + 1) % big] for i in range(big)]) == 1
    print("all tests passed")

Complexity

  • Time: O(V + E). Building both adjacency lists, each DFS pass, and the component in-degree scan each touch every vertex and edge a constant number of times. The final sort is O(k log k) for k answers, at most O(V log V); drop it if order does not matter.
  • Space: O(V + E) for the forward and reversed adjacency lists, plus O(V) for the finish order, component labels and explicit stacks.

Test cases

  • n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] (a DAG) -> [0, 3].
  • n = 3, edges = [[0,1],[1,2],[2,0]] (one cycle) -> [0]. The in-degree rule would wrongly return [].
  • n = 4, edges = [[0,1],[1,0],[2,3],[3,2],[3,0]] -> [2]. Cycle {2,3} reaches cycle {0,1}.
  • n = 4, edges = [[1,1]] -> [0, 1, 2, 3]. A self-loop is not an incoming edge from another component.
  • n = 1, edges = [] -> [0]; n = 0, edges = [] -> [].
  • n = 3, edges = [[0,1],[0,1],[1,2]] (duplicate edge) -> [0].
  • A chain of 200,000 vertices -> [0]. Checks that the DFS is iterative.
  • A single cycle of 200,000 vertices -> count 1.

Follow-ups

  • Return only the count, or any valid set. Use the shortcut: after the first pass, run forward DFS from vertices in decreasing finish time and count the roots. No reversed graph or condensation needed, though the reversed pass is still the cleanest way to get smallest ids.
  • Each vertex has an activation cost; minimize total cost. Still one start per source component, and the components are independent, so pick the cheapest vertex in each source SCC. Replace "smallest id" with "minimum cost".
  • Only some vertices are allowed as starts. Every vertex is downstream of some source component, so the answer is still one start per source component: pick any allowed vertex inside it. If a source component has no allowed vertex, nothing outside can reach it, so report it as impossible (return those components). Allowed vertices in non-source components are never needed.
  • Fewest edges to add so one vertex reaches everything (or the graph becomes strongly connected). With s source components and t sink components in the condensation, making one start reach all needs s - 1 edges from a chosen root. Making the whole graph strongly connected needs max(s, t) edges, or 0 if there is one component (the classic Eswaran-Tarjan result).
  • Edges stream in over time; keep the answer current. Adding an edge u -> v can only merge SCCs or remove sources. Recompute lazily with an O(V + E) pass per query batch, or, for the DAG-only case, keep in-degree counts and update the source set in O(1) per edge. Fully dynamic SCC maintenance is a research topic; mentioning it is enough.

Interviewer expectations

Mid-level (L4)

  • Solves the DAG case with in-degree zero and explains why it works.
  • Spots that cycles break the in-degree rule when given the cycle example, and reaches for SCCs or the finish-order trick with a hint.
  • Writes a correct DFS and handles isolated vertices.

Senior (L5)

  • Asks about cycles up front and goes straight to SCC condensation with a clear proof that one start per source component is necessary and enough.
  • Implements Kosaraju or Tarjan cleanly in O(V + E), iteratively or with a note about recursion depth.
  • Handles self-loops, duplicate edges and deterministic output without prompting.

Staff (L6+)

  • Gives the finish-order shortcut and explains the invariant behind it.
  • Handles the cost and restricted-start follow-ups quickly by reducing them to choices inside source components, and knows that a "reach at least k vertices" variant is NP-hard.
  • Discusses scale: memory of two adjacency lists for very large graphs, streaming edges, and what a distributed version (for example label propagation on a service dependency graph) would look like.

Sign in to comment, vote or remix.