## Saturday, May 23, 2015

### Strongly Connected Components : Kosaraju’s algorithm Implementation - Java

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

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{
String s = null;

marked = new boolean[V];
reg = new int[V];

String d[] = s.split(" ");
int from, to;
from = Integer.parseInt(d[0]);
to = Integer.parseInt(d[1]);

}

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);
}
}
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{
String s = null;

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];

while(E-->0){
String d[] = s.split(" ");
int from, to;
from = Integer.parseInt(d[0]);
to = Integer.parseInt(d[1]);

}

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