Check if adding an edge to a DAG results in a cycle On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest in 2011 organised by Warsaw School of Computer Science.

I have a graph with $V$ $(1 \le V \le 5 \cdot 10^5)$ vertices without edges and a list of $E$ $(1 \le E \le 5 \cdot 10^5)$ directed edges. On the $i$-th second $i$-th edge is being added to a graph. I want to know after which second there will be a cycle in a graph.

The most obvious solution would be to perform DFS after adding each edge, but it would take $O((V + E)^2)$ time. Another solution would be to keep the graph topologically sorted and when adding an edge, I could place it in such a way so that it will not disturb topological ordering. This would take at most $O(V^2)$ time. I did some research on Google and it seems that this is the fastest online algorithm.

As I know all the edges beforehand I can use offline algorithm. The fastest offline algorithm I can think of is binary search. If after $k$-th second graph contains a cycle then obviously it will have a cycle at any other second $l \ge k$. So I can do binary search to find smallest $k$ by performing DFS $O(\log E)$ times, each of them taking $O(V + E)$ time, so the total complexity of this solution would be $O((V + E) \log E)$.

It is quite fast, but I wonder if there exist any faster offline algorithm. One thing I can think of is giving for each edge weight equal to the time when this edge was added to a graph. Then the task would be equivalent to finding a cycle with minimal maximum edge weight. I don't know if it leads to anywhere.
Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well.  I use it for cycle checking, where an actual topological sort is not needed.  In this variant, nodes are discarded as they are visited, instead of being added to the output, and the error termination indicates at least one cycle.  

It works by pruning off root or leaf nodes (having in-degree or out-degree 0 resp.) from the graph one at a time, until no more nodes of that type can be found.  Since this process cannot cut a cycle (all nodes on a cycle have indegree and outdegree > 0), it terminates with a nonempty graph if at least one cycle exists.

If we cut the maximum remaining edge e at each such termination point, we can continue the process to see if E\e still contains a cycle, and so on iteratively until we've cut enough edges to make E acyclic.  The last such edge cut k is the first k that makes E[1...k] cyclic.  

Kahn's algorithm does this leaf-cutting process linearly by using a work queue of nodes to be deleted; it is initialized with the leaves of the entire graph (at least one of which must exist, if it's acyclic), and, as each is deleted, its parent node(s) are checked to see they in turn become leaves, and if so they are added to the work queue.  By checking the neighborhood of each deletion, it works linearly through the graph, without the need for indexing structures beyond the FIFO queue.

We can do the same neighbor-leafness check as we cut the maximum edge, and add any leaves created to the work queue, or, if none are created, continue cutting. 

In order to make the max-cutting process linear, we have to find the maximum non-deleted edge via a descending scan of the edges array, but each scan starts where the previous left off, and the algorithm only does a single pass through the whole array, so that part is O(E) in total.  Overall I believe this method is O(V+E), the same as Kahn's alone.