Graph find all vertices that are part of a cycle

Question

I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices.

Thanks for your help!

Answer 1

There is a duplicate question in StackOverflow. I quote the highest voted answer from Craig Gidney here.

What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.

Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.

Answer 2

I just had an exam. There is the same question, we being ask to find all vertex that not part of cycle.

The function is like this (In C)

void HasCycle(int hasCycle[], int size, Graph g);

In my function, I use

1. An array to track visit status(Using hasCycle provided).

Then I will run DFS on the vertex has not being vsisited, and in each DFS search I kept the following

1. An array to track parent. For example, I visit 3 through edge 5->3, I will put parent[3] = 5.
2. An array to track backedge. The authentic way should be using a timeStamp, this can be found in CLRS, chapter discuss Graph DFS search. I used color. At begin of loop, I color the vertex and at the end, I decolor the vertex so that it can be visited for multiple times. And by this, each time I have a edge conenct two colored node, means there is a back edge.
3. A 2-D matrix, that track the status of edge. Idea is once DFS used the edge, it will be marked so won't do DFS again through that edge. In this way DFS can visit same node for several times but can't using same edge. At the end, I want to achieve, node can be visited several times but have to through different edge.

So that in the end. The time complexity will be O(V^2), for each DFS I run, it will versify the cycle in that connected component. And I will only run DFS if I havn't visit that node in previous DFS.

I am unable to proof the correctness of this algorithm. I did pass the autotest in the exam. So if there is some problem you spotted, just point it out.