Tracking cycles while adding random edges to a sparse graph
Possible solution I came up with while in the shower.
What I will do is maintain a list of size n, representing how many times that node has been on an edge.
When I add an edge (i,j), I will increment list[i] and list[j].
If after an edge addition, list[i] > 1, and list[j] > 1, I will do a DFS starting from that edge.
I realized I don't need to BFS, I only need to DFS from the last added edge, and I only need to do it if it at least has potential to be in a cycle (it's nodes show up twice).
I doubt it is optimal.. maybe some kind of list of disjoint sets would be better.  But this is way better than anything I was thinking of before.
Scenario:  I have a graph, represented as a collection of nodes (0...n).  There are no edges in this graph.
To this graph, I connect nodes at random, one at a time.  An alternative way of saying this would be that I add random edges to the graph, one at a time.
I do not want to create simple cycles in this graph.
Is there a simple and/or very efficient way to track the creation of cycles as I add random edges?  With a graph traversal, it is easy, since we only need to track the two end nodes of a single path.  But, with this situation, we have any number of paths that we need to track - and sometimes these paths combine into a larger path, and we need to track that too.
I have tried several approaches, which mostly come down to maintaining a list of "outer nodes" and a set of nodes internal to them, and then when I add an edge going through it and updating it.  But, it becomes extremely convoluted, especially if I remove an edge in the graph.
I have attempted to search out algorithms or discussions on this, and I can't really find anything.  I know I can do a BFS to check for cycles, but it's so so so horribly inefficient to BFS after every single edge addition.