强连通分量

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/ 更改为我的代码，并增加了输入机会。我问了这个，一位朋友说“这是添加 w 后 addEdge 方法中两个代码的输出，在您的代码中 w 被添加到所有元素，而在原始代码中仅添加到图 v” 但我不知道该怎么做

Answer 1

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

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

当我们查看 Java-Documentation 时，我们阅读了数组中方法 public static void fill(Object[] a, Object val) 的以下内容：

Assigns the specified Object reference to each element of the specified array of Objects.

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

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

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

强连通分量

Strongly Connected Components

java

algorithm

strongly-connected-graph