379. A Cycle You Cannot Escape
The edges are directed. Print Yes if the graph contains a directed cycle,
meaning a route that follows arrows and returns to where it started, and No
otherwise.
The undirected method from problem 365 does not carry over. There, an edge to
an already visited vertex meant a cycle. Here it does not: in 1→2, 1→3, 2→4,
3→4, vertex 4 is reached twice and there is no cycle anywhere, because the
two routes never lead back.
The clean way to decide it is peeling. Repeatedly remove a vertex with in-degree 0, since nothing points at it and it cannot be part of a cycle, then remove its outgoing edges and look again. If every vertex peels away, the graph is acyclic. Whatever remains is holding itself up, and that is a cycle.
This is Kahn's algorithm, and problem 380 turns the order it removes vertices in into an answer of its own.
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.