/*This is a Java Program to Implement Kosaraju Algorithm. Kosaraju’s algorithm is a linear time algorithm to find the strongly connected components of a directed graph.*/

/**
 ** Java Program to Implement Kosaraju Algorithm
 **/

import java.util.*;

/** class Kosaraju **/
public class Kosaraju
{
    /** DFS function **/
    public void DFS(List<Integer>[] graph, int v, boolean[] visited, List<Integer> comp)
    {
        visited[v] = true;
        for (int i = 0; i < graph[v].size(); i++)
            if (!visited[graph[v].get(i)])
                DFS(graph, graph[v].get(i), visited, comp);
        comp.add(v);
    }
    /** function fill order **/
    public List<Integer> fillOrder(List<Integer>[] graph, boolean[] visited)
    {
        int V = graph.length;
        List<Integer> order = new ArrayList<Integer>();
        for (int i = 0; i < V; i++)
            if (!visited[i])
                DFS(graph, i, visited, order);
        return order;
    }
    /** function to get transpose of graph **/
    public List<Integer>[] getTranspose(List<Integer>[] graph)
    {
        int V = graph.length;
        List<Integer>[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList<Integer>();
        for (int v = 0; v < V; v++)
            for (int i = 0; i < graph[v].size(); i++)
                g[graph[v].get(i)].add(v);
        return g;
    }
    /** function to get all SCC **/
    public List<List<Integer>> getSCComponents(List<Integer>[] graph)
    {
        int V = graph.length;
        boolean[] visited = new boolean[V];
        List<Integer> order = fillOrder(graph, visited);
        /** get transpose of the graph **/
        List<Integer>[] reverseGraph = getTranspose(graph);
        /** clear visited array **/
        visited = new boolean[V];
        /** reverse order or alternatively use a stack for order **/
        Collections.reverse(order);
        /** get all scc **/
        List<List<Integer>> SCComp = new ArrayList<>();
        for (int i = 0; i < order.size(); i++)
            {
                /** if stack is used for order pop out elements **/
                int v = order.get(i);
                if (!visited[v])
                    {
                        List<Integer> comp = new ArrayList<>();
                        DFS(reverseGraph, v, visited, comp);
                        SCComp.add(comp);
                    }
            }
        return SCComp;
    }
    /** main **/
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Kosaraju algorithm Test\n");
        Kosaraju k = new Kosaraju();
        System.out.println("Enter number of Vertices");
        /** number of vertices **/
        int V = scan.nextInt();
        List<Integer>[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList<Integer>();
        System.out.println("\nEnter number of edges");
        int E = scan.nextInt();
        /** all edges **/
        System.out.println("Enter "+ E +" x, y coordinates");
        for (int i = 0; i < E; i++)
            {
                int x = scan.nextInt();
                int y = scan.nextInt();
                /** add edge **/
                g[x].add(y);
            }
        System.out.println("\nSCC : ");
        /** print all strongly connected components **/
        List<List<Integer>> scComponents = k.getSCComponents(g);
        System.out.println(scComponents);
    }
}

/*
Enter number of Vertices
8

Enter number of edges
14
Enter 14 x, y coordinates
0 1
1 2
2 3
3 2
3 7
7 3
2 6
7 6
5 6
6 5
1 5
4 5
4 0
1 4

SCC :
[[1, 4, 0], [7, 3, 2], [5, 6]]