Several of the suggested algorithms were in fact implemented in the various Cuckoo Cycle solvers [2]. But by maintaining directed paths, my union-find based algorithm did identify the entire cycle and not just the cycle completing edge [1] (implemented in [3]).
This algorithm suffers from three problems though. One, it only finds one among a set of interconnected cycles. Second, it's rather slow, being latency bound by the random memory accesses. Third, it uses much more memory than needed.
So repeatedly trimming edges with only one endpoint is a much faster approach. And for the random graphs that the PoW generates, it can be done using only 1 bit per edge to record if it's been trimmed.
Once sufficiently trimmed, a loop tracing algorithm (like [4] for the Cuckatoo Cycle variant) can find all remaining (simple) cycles.
[1] https://www.semanticscholar.org/paper/Cuckoo-Cycle%3A-A-Memo...
[2] https://github.com/tromp/cuckoo
[3] https://github.com/tromp/cuckoo/blob/master/src/cuckoo/cycle...
[4] https://github.com/tromp/cuckoo/blob/master/src/cuckatoo/gra...