I was trying to find no. of strongly connected components in a graph. I wrote the below algo but it is failing. The count variable stores the no.of connected components. Count variable is incremented:
- when any unvisited vertex is found (line 1 in code) and then for that vertex dfs is performed
- when no edge going out of the subtree with the lowest arrival time lower than the arrival time of the vertex itself is found (line 2 in code)
I have tried to comment my code. Please tell where I am wrong.
int noOfStronglyConnectedComp(int V, vector<int> adj[])
{
vector<bool> visited(V,false);
vector<int> arr(V); //arrival time of a vertex: when a vertex is first reached
int timer=0; //allocated to arrival time
int count=0; //stores no. of connected components
for(int i=0;i<V;i++)
{
if(!visited[i])
{
count++; //line 1
dfs(i,adj,visited,arr,timer,count,i);
}
}
return count;
}
int dfs(int source,vector<int> adj[], vector<bool> &visited,vector<int> &arr, int &timer, int &count,int parent)
{
visited[source]=1; //node marked visited
arr[source]=timer++; //arrival time is set
int lowest=arr[source]; //lowest stores the edge going out of the subtree with the lowest arrival time
for(int i=0;i<adj[source].size();i++)
{
if(!visited[adj[source][i]])
lowest=min(lowest,dfs(adj[source][i],adj,visited,arr,timer,count,parent));
else
lowest=min(lowest,arr[adj[source][i]]);
}
if(lowest==arr[source] && source!=parent)
count++; //line 2
return lowest;
}