Strongly Connected Components using single DFS. Print Code segment.

SingleDFS.cpp

void Graph::printSCCs()
{
    stack<int> Stack;
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    for(int i = 0; i < V; i++)
        if(visited[i] == false)
            fillOrder(i, visited, Stack);
    Graph gr = getTranspose();
    for(int i = 0; i < V; i++)
        visited[i] = false;
        
    while (Stack.empty() == false)
    {
        // Pop a vertex from stack
        int v = Stack.top();
        Stack.pop();
 
        // Print Strongly connected component of the popped vertex
        if (visited[v] == false)
        {
            gr.DFSUtil(v, visited);
            cout << endl;
        }
    }
}

i think finding reverse of the graph is not allowed in this algorithm...

by amit

The single DFS implementation is a better version of Kosaraju's 2 pass algorithm, Have a look at that. The single DFS algorithm is called Tarjan's SCC Algorithm. Have a look here.

[1] http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

but my question is that we cant transpose the given graph which i think you are doing in line 10

ignoring that line shouldn't really matter because it is not used anywhere in the program. I just re-modified the Kosaraju's 2 pass algorithm in which we do a graph reversal.

void Graph::printSCCs()
{
    stack<int> Stack;
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    for(int i = 0; i < V; i++)
        if(visited[i] == false)
            fillOrder(i, visited, Stack);

    for(int i = 0; i < V; i++)
        visited[i] = false;

    while (Stack.empty() == false)
    {
        // Pop a vertex from stack
        int v = Stack.top();
        Stack.pop();

        // Print Strongly connected component of the popped vertex
        if (visited[v] == false)
        {
            gr.DFSUtil(v, visited);
            cout << endl;
        }
    }
}

Have a look at this. https://sites.google.com/site/indy256/algo/scc_tarjan