Alive Nodes - Count Reachable Nodes in a Directed Graph After Edge Failures

Question

## Round 1 - Coding

## Problem

You are given a directed graph of `n` nodes and a list of edges. Some edges randomly fail (given as a separate list). A node is "alive" if it is reachable from node `0` using only non-failed edges. Return the count of alive nodes.

```python
def count_alive_nodes(
    n: int,
    edges: list[tuple[int, int]],
    failed_edges: list[tuple[int, int]]
) -> int:
    # n: number of nodes (0-indexed)
    # edges: list of (src, dst) directed edges
    # failed_edges: subset of edges that have failed
    # Returns count of nodes reachable from node 0 via non-failed edges
    ...
```

```
Example:
n = 5
edges        = [(0,1), (0,2), (1,3), (2,3), (3,4)]
failed_edges = [(0,2), (1,3)]

Active edges: (0,1), (2,3), (3,4)
From node 0: can reach 1 via (0,1); cannot reach 2, 3, 4
alive nodes: {0, 1}

count_alive_nodes(5, edges, [(0,2),(1,3)]) -> 2
```

## Follow-ups

1. What traversal algorithm (BFS vs. DFS) did you choose and why?
2. How would you handle the case where edges fail dynamically (one at a time) and you must answer queries after each failure?
3. How would you extend this to undirected graphs?
4. What is the time complexity if `failed_edges` can be up to O(E)?

Alive Nodes - Count Reachable Nodes in a Directed Graph After Edge Failures

Question Details

Full Details

Topics

More from DoorDash