Strongly Connected Components : Kosaraju’s algorithm Implementation - Java

Helpful links for algorithm exaplanation :

http://www.geeksforgeeks.org/strongly-connected-components/

Source:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class KosarajuSharirStronglyConnectedComponents {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=0;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new FileReader("e:\\inputVideo.txt"));
        String s = null;
        
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());
        
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while((s=br.readLine())!=null){
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i])groupNo++;
            dfs2(i); 
        }
        
        for(int i=0;i<reg.length;++i){
            System.out.println("Node "+i+" group = "+reg[i]);
        }
    } 
}

Input Format:

Number of vertices V

Number of edges     E

Directed edges Node-from to Node-to

.

.

.

Eth edge

Input File (2 tests):

File #1 Contents:

13

20

0 1

0 5

2 0

2 3

3 2

3 5

4 2

6 0

6 8

6 4

6 9

7 6

7 9

8 6

9 10

9 11

10 12

11 12

11 4

12 9

File #2 Contents (Example case geeksforgeeks):

5

5

1 0

0 2

2 1

0 3

3 4

Output:

For Test #1:

[1, 2, 4, 3, 0]

Node 0 group = 1

Node 1 group = 1

Node 2 group = 1

Node 3 group = 2

Node 4 group = 3

For Test #2:

[1, 5, 0, 3, 2, 4, 8, 12, 10, 11, 9, 6, 7]

Node 0 group = 6

Node 1 group = 8

Node 2 group = 5

Node 3 group = 5

Node 4 group = 4

Node 5 group = 7

Node 6 group = 2

Node 7 group = 1

Node 8 group = 2

Node 9 group = 3

Node 10 group = 3

Node 11 group = 3

Node 12 group = 3

Practice problems: SPOJ: http://www.spoj.com/problems/WEBISL/

Solution :Java: AC:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class WEBISL {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=-1;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    static int[] groups;
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        if(groups[groupNo]>vertex)groups[groupNo]=vertex;
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        
        String[] fD = br.readLine().split(" ");
        V = Integer.parseInt(fD[0]);
        E = Integer.parseInt(fD[1]);
        groups = new int[V];
        Arrays.fill(groups, Integer.MAX_VALUE);
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while(E-->0){
            s = br.readLine();
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
//        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i]){groupNo++;}
            dfs2(i); 
        }
         
        for(int i=0;i<reg.length;++i){
            System.out.println(groups[reg[i]]);
        }
//        System.out.println(Arrays.toString(groups));
//        System.out.println(Arrays.toString(reg));
    } 
}