Check if adding an edge to a DAG results in a cycle
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.