PreviousNext
Coding/Graphs and trees

Make graph strongly connected

Write codeHard40 minCitadel style

Your task

Given a directed graph on n nodes (0..n-1) with a list of directed edges, return the minimum number of directed edges you must add so that the whole graph becomes strongly connected (every node reachable from every other). If it is already strongly connected, return 0. Constraints: 1 <= n <= 2000; edges may contain self-loops or duplicates.

Examples

min_edges_to_strongly_connect(n: int, edges: list[list[int]]) -> int
Example 1
Inputmin_edges_to_strongly_connect(5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]])
Output1