Cycle in graph

general
1

How to detect cycle in a graph which is disconnected?
Can it be done by dfs??If possible how

2

This might help…If have any doubt please feel free to ask.

Link

3

By disconnected you mean, the graph may be both disconnected for some nodes and connected for others. You can use DFS for finding cycle. However, if the graph is directed, you can use topological sort also for doing the same.

//find the indegree of all the nodes.
for(i=0;i<V;i++)
 if(indegree[i]==0)
   enqueue(Q,i);

while(!Q.empty())
{
  v= dequeue(Q)
  topologicalsort[v]== +counter;
  for all neighbours w of v:
    indegree[w]--;
    if(indegree[w]==0)
      enqueue(Q,w);
}

if(counter!=V)
 cout<<"A cycle exists\n";

If any mistake or anything unclear, you may ask… :slight_smile:

4

You have to mark each component you visit and then when you are over with the bfs on one of the subgraphs you just go to the other one.