Edge Reversal: Reverse All Edges in a Directed Graph and Find New Strongly Connected Components

Question

## Problem

Given a directed graph as an adjacency list, produce its transpose (reverse all edge directions), then determine whether the set of strongly connected components (SCCs) changes. Return the transposed graph and the SCCs of both the original and transposed graph.

```python
def analyze_reversal(
    graph: dict[int, list[int]]
) -> dict:
    # Returns {
    #   "transposed": dict[int, list[int]],
    #   "original_sccs": list[list[int]],
    #   "transposed_sccs": list[list[int]]
    # }
    pass
```

**Example:**
```
graph = {1:[2], 2:[3], 3:[1], 4:[3]}
transposed = {2:[1], 3:[2], 1:[3], 3:[4]}
original_sccs  = [[1,2,3], [4]]
transposed_sccs = [[1,2,3], [4]]  # same SCCs, by Kosaraju's property
```

## Follow-ups

1. Kosaraju's algorithm for SCCs uses the transposed graph as a key step. Explain why the finishing order from the first DFS on the original graph is used to drive the second DFS on the transpose.
2. Prove or disprove: a directed graph and its transpose always have identical SCCs.
3. What is the time complexity of Kosaraju's algorithm, and how does Tarjan's algorithm compare?
4. If the graph has 10 million nodes, what memory layout makes the DFS stack-safe and cache-friendly?

Edge Reversal: Reverse All Edges in a Directed Graph and Find New Strongly Connected Components

Question Details

Full Details

Topics

More from Uber