> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/strongly-connected-components.md).

# Strongly Connected Components

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.

[![SCC](https://media.geeksforgeeks.org/wp-content/cdn-uploads/SCC.png)](https://media.geeksforgeeks.org/wp-content/cdn-uploads/SCC.png)

We can find all strongly connected components in O(V+E) time using [Kosaraju’s algorithm](http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm). Following is detailed Kosaraju’s algorithm.\
**1)** Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.\
**2)** Reverse directions of all arcs to obtain the transpose graph.\
**3)** One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call [DFSUtil(v)](https://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/)). The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1 (One by one popped from stack).<br>

```java
public class solution {
    public static void fillStackDFS(int v, ArrayList<Integer>[] graph, Stack<Integer> st, boolean[] visited) {
        visited[v] = true;
        for (int x : graph[v])
            if (!visited[x])
                fillStackDFS(x, graph, st, visited);
        st.push(v);
    }

    public static void fillStack(ArrayList<Integer>[] graph, Stack<Integer> st) {
        boolean visited[] = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++)
            if (!visited[i])
                fillStackDFS(i, graph, st, visited);
    }

    public static ArrayList<Integer>[] reverseGraph(ArrayList<Integer>[] graph) {
        ArrayList<Integer>[] graphReverse = new ArrayList[graph.length];
        for (int i = 0; i < graph.length; i++)
            graphReverse[i] = new ArrayList<>();
        for (int i = 0; i < graph.length; i++)
            for (int x : graph[i])
                graphReverse[x].add(i);
        return graphReverse;
    }

    public static void findSCCDFS(int v, ArrayList<Integer>[] graph, boolean[] visited, ArrayList<Integer> SCC) {
        visited[v] = true;
        SCC.add(v);
        for (int x : graph[v])
            if (!visited[x])
                findSCCDFS(x, graph, visited, SCC);
    }

    public static ArrayList<ArrayList<Integer>> allSCComponents(Stack<Integer> st, ArrayList<Integer>[] graph) {
        boolean visited[] = new boolean[graph.length];
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        while (st.size() != 0) {
            int v = st.pop();
            if (!visited[v]) {
                ArrayList<Integer> SCC = new ArrayList<>();
                findSCCDFS(v, graph, visited, SCC);
                ans.add(SCC);
            }
        }
        return ans;
    }

    public static ArrayList<ArrayList<Integer>> findAllSCC(ArrayList<Integer>[] graph) {
        Stack<Integer> st = new Stack<>();
        fillStack(graph, st);
        ArrayList<Integer>[] graphReverse = reverseGraph(graph);
        return allSCComponents(st, graphReverse);
    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int v = s.nextInt();
        int e = s.nextInt();
        ArrayList<Integer>[] graph = new ArrayList[v];
        for (int i = 0; i < graph.length; i++)
            graph[i] = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            int v1 = s.nextInt();
            int v2 = s.nextInt();
            graph[v1].add(v2);
        }
        ArrayList<ArrayList<Integer>> ans = findAllSCC(graph);
        for (ArrayList<Integer> x : ans) {
            for (int elem : x)
                System.out.print(elem + " ");
            System.out.println();
        }
        s.close();
    }
}
```