Strongly Connected | Practice Medium 0 attempts
GeeksforGeeks ↗

Strongly Connected | Practice

Medium GraphBFSDFS GeeksforGeeks

In a directed graph, a strongly connected component is a set of vertices where every vertex can reach every other vertex in the set by following directed edges. Given such a graph, find and return all of its strongly connected components.

Input Format
Implement findSCCs(V, adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Order inside each group does not matter either.

Sample Input and Output

Example 1 ยท Run Sample

Input
V = 5
adj = [[1],[2],[0,3],[4],[]]
Output
[[0,1,2],[3],[4]]

Example 2

Input
V = 1
adj = [[]]
Output
[[0]]
Constraints
  • 1 <= V <= 5000
  • 0 <= E <= V*(V-1)
Test Cases (2)
Case 1
Args: [5,[[1],[2],[0,3],[4],[]]] Expected: [[0,1,2],[3],[4]]
Case 2
Args: [1,[[]]] Expected: [[0]]
Topics
GraphBFSDFS

Iterative Kosaraju

Use explicit DFS frames to record vertices in finishing order. Traverse the reversed graph in reverse finishing order; each traversal yields one strongly connected component.

javascript
function findSCCs(V, adj) {
  const visited=Array(V).fill(false),order=[],reverse=Array.from({length:V},()=>[]);
  for(let u=0;u<V;u++)for(const v of adj[u])reverse[v].push(u);
  for(let start=0;start<V;start++)if(!visited[start]){
    const stack=[[start,0]];visited[start]=true;
    while(stack.length){const frame=stack[stack.length-1],u=frame[0];if(frame[1]===adj[u].length){order.push(u);stack.pop();continue;}const v=adj[u][frame[1]++];if(!visited[v]){visited[v]=true;stack.push([v,0]);}}
  }
  visited.fill(false);const result=[];
  while(order.length){const start=order.pop();if(visited[start])continue;const stack=[start],component=[];visited[start]=true;
    while(stack.length){const u=stack.pop();component.push(u);for(const v of reverse[u])if(!visited[v]){visited[v]=true;stack.push(v);}}
    result.push(component);
  }
  return result;
}

Time: O(V + E) | Space: O(V + E)

Saved in this browser only. Private to you.

JavaScript