Search code examples
algorithmgraphcycledepth-first-search

Find all vertices in an undirected graph that belong to any cycle

Is there a way to find all vertices that are a part of a simple cycle in a graph in linear time?

I found a way to do it in O(|V|(|V|+|E|)) time but was wondering if there is a way to do it faster?

Solution

  • Ok, I think I have the answer. while processing DFS, for every vertex v calculate low(v) (explained below). then running DFS once again and check for every vertex v:

    if low(v) != d(v) (where d(v) is the distance from the DFS tree root)

    vertex v is a part of a simple cycle.

    *low(v) = min ( d(v),d(u),low(w)) where (v,u) is a back edge and w is a child of v in the DFS tree. calculated in O(|V|+|E|) time.