« back

Strongly connected component (Tarjans's Algo)

Tags : graph, greedy, geeksforgeeks, cpp, hard

Problem Statement - link #

Given a Directed Graph with V vertices and E edges, Find the members of strongly connected components in the graph.

Your Task: You don’t need to read input or print anything. Your task is to complete the function tarjans() which takes the number of vertices V and adjacency list of the graph as input parameters and returns a list of list of integers denoting the members of strongly connected components in the given graph. Note: A single strongly connected component must be represented in the form of a list if integers sorted in the ascending order. The resulting list should consist of a list of all SCCs which must be sorted in a way such that a lexicographically smaller list of integers appears first.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:


Input:

Output:
0 1 2,3,4,
Explanation:


We can clearly see that there are 3 Strongly
Connected Components in the Graph as mentioned
in the Output.

Constraints #

Solutions #

class Solution
{
    vector<vector<int>> res;
    void TASCCUtil(int u, vector<int> adj[], int disc[], int low[], stack<int> &st, bool stMember[]) {
        static int time = 0;
        disc[u] = low[u] = ++time;
        stMember[u] = true;
        st.push(u);
        for (int v: adj[u]) {
            if (disc[v] == -1) {
                TASCCUtil(v, adj, disc, low, st, stMember);
                low[u] = min(low[u], low[v]);
            } else if (stMember[v] == true) {
                low[u] = min(low[u], disc[v]);
            }
        }
        int w=0;

        if (low[u] == disc[u]) {
            vector<int> temp;
            while (st.top() != u) {
                w = st.top();
                temp.push_back(w);
                st.pop();
                stMember[w] = false;
            }
            w = st.top();
            temp.push_back(w);
            st.pop();
            stMember[w] = false;
            sort(temp.begin(),temp.end());
            res.push_back(temp);
        }
    }
	public:
    //Function to return a list of lists of integers denoting the members 
    //of strongly connected components in the given graph.
    vector<vector<int>> tarjans(int V, vector<int> adj[])
    {
        //code here
        int *disc = new int[V];
        int *low = new int[V];
        stack<int> st;
        bool *stMember = new bool[V];
        for (int i = 0; i < V; i++) {
            disc[i] = -1;
            stMember[i] = false;
        }
        for (int i = 0; i < V; i++) {
            if (disc[i] == -1) {
                TASCCUtil(i, adj, disc, low, st, stMember);
            }
        }
        sort(res.begin(),res.end());
        return res;
    }
};