400. Everyone Can Reach Everyone
The last problem of the topic, and it uses almost everything in it.
The edges are directed. Print Yes if EVERY vertex can reach every other
vertex by following arrows, and No otherwise. A graph like that is called
strongly connected.
Running problem 395's method from every vertex would be O(n × (n + m)), and
here n is large. Two searches suffice, and the argument is worth following:
1. Search forwards from vertex 1. If it does not reach everything, some vertex
cannot be reached from vertex 1, so the answer is No.
2. Search from vertex 1 along every edge REVERSED. Reaching a vertex v
backwards means v can reach vertex 1 forwards. If this does not reach
everything, some vertex cannot reach vertex 1, so the answer is No.
If both succeed, take any two vertices u and v: u reaches 1 by step 2 and
1 reaches v by step 1, so u reaches v. That holds for every pair, which
is exactly the definition.
So build two adjacency lists while reading, one per direction, and traverse each once.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
directed edges. Each of the next m lines contains two integers u and v,
a directed edge from u to v and NOT from v to u. Vertices are numbered
1 to n.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.