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.

We can find all strongly connected components in O(V+E) time using Kosaraju’s 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)). 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).

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