Collapsing every strongly connected component to one node turns any directed graph into a condensation: a graph with no cycles at all. A component with no incoming edge in the condensation is a source, one with no outgoing edge is a sink.
Write min_edges_to_strengthen(n, edges) returning the smallest number of directed edges that have to be added to make the whole graph strongly connected. A graph that is already strongly connected needs 0.
Examples
Input: n = 3, edges = [(0, 1), (1, 2)]
Output: 1
Explanation: one edge from 2 back to 0 closes the loop.
Input: n = 3, edges = [(0, 1), (0, 2)]
Output: 2
Explanation: there is one source and two sinks, and each sink needs a way out.
Constraints
1 <= n <= 2 * 10**4,0 <= len(edges) <= 10**5- A single node with no edges is already strongly connected.
Goals
- Collapse each component to a single node and see the DAG underneath
- Count the components with nothing coming in and nothing going out
- Prove to yourself why the answer is the larger of those two counts