Skip to content

Instantly share code, notes, and snippets.

@sudheesh001
Created November 21, 2013 05:21
Show Gist options
  • Save sudheesh001/7576463 to your computer and use it in GitHub Desktop.
Save sudheesh001/7576463 to your computer and use it in GitHub Desktop.
Strongly Connected Components using single DFS. Print Code segment.
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;
}
}
}
@rajatu
Copy link

rajatu commented Nov 21, 2013

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

@rajatu
Copy link

rajatu commented Nov 21, 2013

by amit

@sudheesh001
Copy link
Author

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

@rajatu
Copy link

rajatu commented Nov 21, 2013

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

@sudheesh001
Copy link
Author

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;
        }
    }
}

@sudheesh001
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment