Java Program to Implement Tarjan Algorithm

Code:

import java.util.*;

/** class Tarjan **/
class Tarjan
{
    /** number of vertices **/
    private int V;    
    /** preorder number counter **/
    private int preCount;
    /** low number of v **/
    private int[] low;
    /** to check if v is visited **/
    private boolean[] visited;      
    /** to store given graph **/
    private List[] graph;
    /** to store all scc **/
    private List> sccComp;
    private Stack stack;

    /** function to get all strongly connected components **/
    public List> getSCComponents(List[] graph) 
    {
        V = graph.length;
        this.graph = graph;
        low = new int[V];
        visited = new boolean[V];
        stack = new Stack();
        sccComp = new ArrayList<>();

        for (int v = 0; v < V; v++)
              if (!visited[v])
                dfs(v);

        return sccComp;
    }
    /** function dfs **/
    public void dfs(int v) 
    {
        low[v] = preCount++;
        visited[v] = true;
        stack.push(v);
        int min = low[v];
        for (int w : graph[v]) 
        {
            if (!visited[w])
                dfs(w);
            if (low[w] < min) 
                min = low[w];
        }
        if (min < low[v]) 
        { 
            low[v] = min; 
            return; 
        }        
        List component = new ArrayList();
        int w;
        do
        {
            w = stack.pop();
            component.add(w);
            low[w] = V;                
        } while (w != v);
        sccComp.add(component);        
    }    
    /** main **/
    public static void main(String[] args)
    {    
        Scanner scan = new Scanner(System.in);
        System.out.println("Tarjan algorithm Test\n");
        System.out.println("Enter number of Vertices");
        /** number of vertices **/
        int V = scan.nextInt();

        /** make graph **/
        List[] g = new List[V];        
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList();        
        /** accpet all edges **/
        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();
            g[x].add(y);
        }

        Tarjan t = new Tarjan();        
        System.out.println("\nSCC : ");
        /** print all strongly connected components **/
        List> scComponents = t.getSCComponents(g);
           System.out.println(scComponents);        
    }    
}


Output:

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 :
[[5, 6], [7, 3, 2], [4, 1, 0]]


More Java Programs: