395. A Vertex That Reaches Everyone
The edges are directed. A vertex is a mother vertex when every vertex in the
graph can be reached from it by following arrows. Print the smallest-numbered
mother vertex, or -1 if there is none.
The direct method is to run the traversal of problem 381 from every vertex and
stop at the first one that reaches all n. That is O(n × (n + m)), which
the constraints here allow on purpose: this problem is about understanding what
is being asked, and the efficient method is a topic of its own.
Do notice that vertex 1 is not special. In the fifth test the mother vertex is 2, and vertex 1 reaches nothing at all.
Constraints - `1 ≤ n ≤ 500` - `0 ≤ m ≤ 5000` - 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 the smallest-numbered mother vertex, or -1 if no vertex reaches all the
others.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.