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
- 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
- An array to track parent. For example, I visit 3 through edge 5->3, I will put parent[3] = 5.
- 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.
- 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.