Finding no. of strongly connected components - wrong answer by my code

97 views Asked by At

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:

  1. when any unvisited vertex is found (line 1 in code) and then for that vertex dfs is performed
  2. 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;    
    }
0

There are 0 answers