Tarjan's Algorithm to find Strongly Connected Components - GeeksforGeeks

Tarjan's Algorithm to find Strongly Connected Components - GeeksforGeeks
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph. For example, there are 3 SCCs in the following graph.

Kosaraju’s algorithm for strongly connected components. The previously discussed algorithm requires two DFS traversals of a Graph. In this post, Tarjan’s algorithm is discussed that requires only one DFS traversal.

Tarjan Algorithm is based on following facts:
1. DFS search produces a DFS tree/forest
2. Strongly Connected Components form subtrees of the DFS tree.
3. If we can find head of such subtrees, we can print/store all the nodes in that subtree (including head) and that will be one SCC.
4. There is no back edge from one SCC to another (There can be cross edges, but cross edges will not be used while processing the graph).

To find head of a SCC, we calculate desc and low array (as done for articulation point, bridge,biconnected component). As discussed in the previous posts, low[u] indicates earliest visited vertex (the vertex with minimum discovery time) that can be reached from subtree rooted with u. A node u is head if disc[u] = low[u].

// A recursive function that finds and prints strongly connected

// components using DFS traversal

// u --> The vertex to be visited next

// disc[] --> Stores discovery times of visited vertices

// low[] -- >> earliest visited vertex (the vertex with minimum

//             discovery time) that can be reached from subtree

//             rooted with current vertex

// *st -- >> To store all the connected ancestors (could be part

//           of SCC)

// stackMember[] --> bit/index array for faster check whether

//                  a node is in stack

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,

                    bool stackMember[])

{

    // A static variable is used for simplicity, we can avoid use

    // of static variable by passing a pointer.

    static int time = 0;

 

    // Initialize discovery time and low value

    disc[u] = low[u] = ++time;

    st->push(u);

    stackMember[u] = true;

 

    // Go through all vertices adjacent to this

    list<int>::iterator i;

    for (i = adj[u].begin(); i != adj[u].end(); ++i)

    {

        int v = *i;  // v is current adjacent of 'u'

 

        // If v is not visited yet, then recur for it

        if (disc[v] == -1)

        {

            SCCUtil(v, disc, low, st, stackMember);

 

            // Check if the subtree rooted with 'v' has a

            // connection to one of the ancestors of 'u'

            // Case 1 (per above discussion on Disc and Low value)

            low[u]  = min(low[u], low[v]);

        }

 

        // Update low value of 'u' only of 'v' is still in stack

        // (i.e. it's a back edge, not cross edge).

        // Case 2 (per above discussion on Disc and Low value)

        else if (stackMember[v] == true)

            low[u]  = min(low[u], disc[v]);

    }

 

    // head node found, pop the stack and print an SCC

    int w = 0;  // To store stack extracted vertices

    if (low[u] == disc[u])

    {

        while (st->top() != u)

        {

            w = (int) st->top();

            cout << w << " ";

            stackMember[w] = false;

            st->pop();

        }

        w = (int) st->top();

        cout << w << "\n";

        stackMember[w] = false;

        st->pop();

    }

}

 

// The function to do DFS traversal. It uses SCCUtil()

void Graph::SCC()

{

    int *disc = new int[V];

    int *low = new int[V];

    bool *stackMember = new bool[V];

    stack<int> *st = new stack<int>();

 

    // Initialize disc and low, and stackMember arrays

    for (int i = 0; i < V; i++)

    {

        disc[i] = NIL;

        low[i] = NIL;

        stackMember[i] = false;

    }

 

    // Call the recursive helper function to find strongly

    // connected components in DFS tree with vertex 'i'

    for (int i = 0; i < V; i++)

        if (disc[i] == NIL)

            SCCUtil(i, disc, low, st, stackMember);

}

Read full article from Tarjan's Algorithm to find Strongly Connected Components - GeeksforGeeks