Airport Connections

Tags

Airport Connections

Category

Graphs

Difficulty

Very Hard

Problem Statement

Given a list of airports, a list of one-way routes between them, and a starting airport, find the minimum number of new one-way routes that must be added from the starting airport so that every airport in the list is reachable from the starting airport. The new routes always originate from the starting airport.

Intuition

First, we identify which airports are already reachable from the starting airport. The unreachable airports form subgraphs among themselves. If we can group unreachable airports into strongly connected components (SCCs) and then analyze the DAG of these SCCs, we only need one new route per SCC that has no incoming edge from another unreachable SCC (or from the reachable set). However, a greedy approach is more practical: we compute SCCs of the unreachable subgraph, build a DAG, and count SCC nodes with in-degree 0 in that DAG. Each such node requires one new connection from the starting airport, because no other unreachable SCC feeds into it.

Approach

  1. Find reachable airports: Run BFS/DFS from the starting airport using the existing routes. Mark all reachable airports.
  2. Filter unreachable airports: Collect all airports not reachable from the starting airport.
  3. Build the subgraph of unreachable airports using only routes where both endpoints are unreachable.
  4. Find SCCs of this subgraph using Tarjan's algorithm or Kosaraju's algorithm.
  5. Build the condensation DAG: Each SCC becomes a node. Add a directed edge between SCC nodes if there is a route from an airport in one SCC to an airport in another.
  6. Count source nodes: In the condensation DAG, count nodes with in-degree 0. Each such source SCC requires exactly one new route from the starting airport.
  7. Return that count. If all airports are already reachable, return 0.

Pseudocode

function airportConnections(airports, routes, startingAirport):
    // Step 1: Build adjacency list
    graph = build directed graph from routes

    // Step 2: Find all airports reachable from startingAirport
    reachable = BFS/DFS from startingAirport on graph
    unreachable = airports - reachable

    if unreachable is empty:
        return 0

    // Step 3: Build subgraph of unreachable airports
    subgraph = filter graph to only include edges between unreachable airports

    // Step 4: Find SCCs in subgraph (Kosaraju's or Tarjan's)
    sccs = findSCCs(subgraph, unreachable)

    // Step 5: Build condensation DAG and compute in-degrees
    sccId = map each unreachable airport to its SCC index
    inDegree = array of size |sccs|, initialized to 0
    for each edge (u, v) in subgraph:
        if sccId[u] != sccId[v]:
            inDegree[sccId[v]] += 1
    // Deduplicate edges to avoid over-counting
    // (use a set of (sccId[u], sccId[v]) pairs)

    // Step 6: Count sources
    count = 0
    for each scc index i:
        if inDegree[i] == 0:
            count += 1

    return count

Time & Space Complexity

  • Time: O(V + E) where V is the number of airports and E is the number of routes. BFS/DFS, SCC computation, and condensation DAG construction are all linear.
  • Space: O(V + E) for the graph, SCC data structures, and the condensation DAG.

Key Insights

  • The core insight is that adding a route from the starting airport to any airport in an SCC makes the entire SCC reachable (since all nodes in an SCC can reach each other).
  • Only "source" SCCs (in-degree 0 in the condensation DAG) need new routes. Non-source SCCs are reachable from some other unreachable SCC, which will itself become reachable.
  • The condensation DAG is always a DAG (no cycles), which is what allows the simple in-degree analysis.
  • Routes always originate from the starting airport, which simplifies the problem compared to a general minimum edge augmentation problem.

Edge Cases

  • All airports already reachable: Return 0.
  • No existing routes: Each airport (except the starting one) is its own SCC with in-degree 0, so n - 1 new routes are needed.
  • Single unreachable airport: Exactly 1 new route needed.
  • All unreachable airports form one big SCC: Only 1 new route needed to that SCC.
  • Starting airport has no outgoing routes at all: All other airports are unreachable; need to count source SCCs of the full remaining graph.
  • Airports with no routes at all (isolated nodes): Each isolated node is its own SCC with in-degree 0, each requiring one new route.

Linked mentions