Топологическая сортировка как обратная Post-DFS | Расписание курсов II LeetCode ⇐ JAVA

[Anonymous]

В настоящее время решается расписание курса II на LeetCode, и этот код НЕ ПРОХОДИТ все тестовые случаи из-за следующей строки: Collections.reverse(postOrder);. Удаление этой строки решает все тестовые случаи.

Код: Выделить всё

class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
HashMap graph = new HashMap();

for (int[] pre: prerequisites) {
graph.put(pre[0], new ArrayList());
}

for (int[] pre: prerequisites) {
graph.get(pre[0]).add(pre[1]);
}

boolean visited[] = new boolean[numCourses];
boolean visiting[] = new boolean[numCourses];

ArrayList postOrder = new ArrayList();

for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (!dfs(i, visited, visiting, postOrder, graph)) {
return new int[0];
}
}
}
Collections.reverse(postOrder);
return postOrder.stream().mapToInt(i -> i).toArray();

}

private boolean dfs(Integer v, boolean[] visited, boolean[] visiting, ArrayList postOrder, HashMap graph) {
visiting[v] = true;

if (graph.get(v) != null) {
for (Integer neighbor : graph.get(v)) {
if(visiting[neighbor]) {
return false;
}

if (!visited[neighbor]) {
if (!dfs(neighbor, visited, visiting, postOrder, graph)) {
return false;
}
}
}
}

visiting[v] = false;
visited[v] = true;

postOrder.add(v);
System.out.println(v);
return true;
}
}

Я узнал, что обратный порядок DFS дает правильную топологическую сортировку. Однако, когда я переворачиваю свой список пост-заказов DFS, я получаю неправильный ответ. Я прохожу все тестовые случаи без разворота. Кто-нибудь знает, почему это так? Буду признателен за любую информацию.
Это код main() для воспроизведения неправильного ответа:

Код: Выделить всё

    import java.util.ArrayList;
import java.util.HashMap;

public class Main {
public static void main(String[] args) {
Solution solution = new Solution();

// Test case 1
int numCourses1 = 3;
int[][] prerequisites1 = {{1, 0}};
int[] result1 = solution.findOrder(numCourses1, prerequisites1);
printResult(result1);

// Test case 2
int numCourses2 = 3;
int[][] prerequisites2 = {{0, 1}, {1, 2}, {2, 0}};
int[] result2 = solution.findOrder(numCourses2, prerequisites2);
printResult(result2);
}

private static void printResult(int[] result) {
if (result.length == 0) {
System.out.println("No valid course order.");
} else {
for (int course : result) {
System.out.print(course + " ");
}
System.out.println();
}
}
}

В результате тестового примера 2 ответ, который дает мой код, является обратным фактическому ответу.


Подробнее здесь: https://stackoverflow.com/questions/786 ... i-leetcode