0

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


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”但我不知道如何去做吧

4

1 回答 1

2

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

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

当我们查看Java 文档public static void fill​(Object[] a, Object val)时，我们从 Arrays中读取了以下方法：

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

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

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

for(int i = 0; i < adj.length; i++) {
  adj[i] = new ArrayList<>();
}
于 2021-03-18T20:47:43.723 回答