I’m trying to understand the various optimizations given in the original 1992 paper on Karger’s algorithm. Specifically, looking at section “3.1 Unweighted Graphs”, I don’t understand what data structure is used to represent the variant of the algorithm that works in $O(|E|)$ time and space (the other variant, which uses union-find and takes $O(|V|)$ space and $O(|E| log |E|)$ time, makes sense).
Specifically: how would you represent the edges so that it is possible to
- track the connected components induced by a sequence of $m$ edges in a random order in $O(m)$ time?
- contract a sequence of $m/2$ edges in a random order in $O(m)$ time?
I must be missing something obvious, but I couldn’t find any implementation for this variant (everyone seems mostly interested in implementing the union-find variant of the algorithm).