Detecting cycles in incremental graph

Question

Given that I have an initially empty graph, to which will, incrementally, be added edges (one by one), what would be the best way to detect and identify appearing cycles?

Would I have to check for cycles in the entire graph every time a new edge is added? This approach doesn't take advantage of computations already made. Is there an algorithm that I still haven't found?

Thanks.

Answer 1

You can use the Quick Union Find algorithm here to 1st check whether the two ends of the new edge are already connected.

EDIT:
As noted in the comment, this solution works only for an undirected graph. For a directed graph, following link may help https://cs.stackexchange.com/questions/7360/directed-union-find.