Email list hosting service & mailing list manager

Tarjan's SCC Lassi Kortela (11 Aug 2022 10:47 UTC)
Re: Tarjan's SCC Lassi Kortela (11 Aug 2022 10:50 UTC)
Re: Tarjan's SCC Marc Nieper-Wißkirchen (11 Aug 2022 11:09 UTC)

Tarjan's SCC Lassi Kortela 11 Aug 2022 10:47 UTC

Mentioned by Marc in the other thread,
https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

- Linear time and space complexity

- Implementation looks simple

- Returns a list of cycles in the graph

- The single-node "cycles" comprise the non-cyclic part

- They are returned in reverse order. If we accumulate them into a
linked list, we don't need to `reverse` it at the end.