强连通分量

Question

我出了问题，我的输出不正确

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

    }
}

我的意见：

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

我的产出：

4 3 1 2 0 

产出应如下：

0 1 2
3
4

我甚至不知道为什么会有这样的错误。我将代码从https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/更改为代码，并增加了输入的机会。我问了这个问题，一位朋友说：“这是addEdge方法中两种代码的输出，在添加w之后，在代码中，w被添加到所有元素中，而原始代码只添加到图v中”，但我不知道如何实现。

Answer 1

问题在初始化adj-Array的列表的行中：

Arrays.fill(adj, new ArrayList());

当我们查看Java-文档时，我们从数组中读取了public static void fill​(Object[] a, Object val)方法的如下内容：

将指定的对象引用分配给指定对象数组的每个元素。

这意味着adj-Array中的所有条目都使用相同的列表。在您的示例中，每个节点在右侧至少有一次，因此每个节点都在这一个列表中。

当您用简单的for循环替换上面的行以初始化adj-Array的ArrayLists时，它应该可以工作。

for(int i = 0; i < adj.length; i++) {
  adj[i] = new ArrayList<>();
}