A directed graph is strongly connected when there is a directed path from every node to every other node. Checking every pair is far too slow, but two searches from a single node settle it.
Write strongly_connected(n, edges) returning True or False.
Examples
Input: n = 3, edges = [(0, 1), (1, 2), (2, 0)]
Output: True
Input: n = 3, edges = [(0, 1), (1, 2)]
Output: False
Explanation: nothing leads back from 2 to 0.
Constraints
1 <= n <= 2 * 10**4,0 <= len(edges) <= 10**5- Use an iterative search; the graph can be a chain 20 000 nodes long.
Goals
- Check that one node reaches everything and is reached by everything
- Build the reverse graph and search it
- See why those two searches are enough for the whole graph