I got a problem, my output is not correct
import java.util.*;
import java.util.Scanner;
import java.util.ArrayList;
class StronglyConnectedComponents {
int V; //number of nodes
ArrayList<Integer> adj[]; //adjacenty list
int time;
StronglyConnectedComponents(int v) {
this.V = v;
this.time = 0;
this.adj = new ArrayList[v];
Arrays.fill(adj, new ArrayList()); //adj list of v elements(arrayLists)
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void util(int u, int low[], int disc[], int stackMember[], Stack<Integer> st) {
stackMember[u] = 1; //visited
disc[u] = time; //first time visiting time
low[u] = time++; //after update time +1
st.push(u); //dfs - take last added as first observal vertex
for (Integer i : adj[u]) { //traversing adjacents of u
if (disc[i] == -1) {
util(i, low, disc, stackMember, st);
if (low[u] > low[i]) low[u] = low[i]; //update If node v is not visited
} else if (stackMember[i] != 0) //if i is still in stack update value
{
if (low[u] > disc[i]) low[u] = disc[i];
}
}
int w = -1;
if (low[u] == disc[u]) {
while (w != u) //while there is a path
{
w = (int) st.pop();
stackMember[w] = 0;
System.out.print(w + " ");
}
System.out.println();
}
}
void SCC() {
//first time all vertices has no parent, therefore fill with -1
int disc[] = new int[V];
Arrays.fill(disc, -1);
int low[] = new int[V];
Arrays.fill(low, -1);
int stackMember[] = new int[V];
Stack<Integer> st = new Stack<Integer>();
//all vertices not visited filling
for (int i = 0; i < V; i++) {
if (disc[i] == -1)//if not visited vertex
util(i, low, disc, stackMember, st);
}
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of nodes");
int n = sc.nextInt();
System.out.println("Enter the number of edge");
int m = sc.nextInt();
m++;
StronglyConnectedComponents g = new StronglyConnectedComponents(n);
System.out.println("Enter the edges:");
while (m-- > 0 && sc.hasNext()) {
String[] input = sc.nextLine().split(" ");
if (input.length == 2) {
g.addEdge(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
}
}
g.SCC();
}
}
My input:
Enter the number of nodes
5
Enter the number of edge
5
Enter the edges:
1 0
0 2
2 1
0 3
3 4
my output:
4 3 1 2 0
Output should be like this:
0 1 2
3
4
I dont even know why there is mistake like this. I changed code from https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ to my code, and added opportunity to input. I asked about this and one friend said that "this is the output of both codes in the addEdge method after adding w, in your code w is added to all elements, and in the original only to the graph v" but i dont know how to do it
The problem is in the line where you initialize the Lists for your adj-Array:
Arrays.fill(adj, new ArrayList());
When we take a look at the Java-Documentation we read the following for the method public static void fill​(Object[] a, Object val) from Arrays:
Assigns the specified Object reference to each element of the specified array of Objects.
This means all of the entries in your adj-Array use the same list. In your example every node is at least one time on the right side, and therefore every node is in this one list.
When you replace the line above with a simple for loop to initialize the ArrayLists for the adj-Array, it should work.
for(int i = 0; i < adj.length; i++) {
adj[i] = new ArrayList<>();
}