Topological Sort as Reverse Post-DFS | Course Schedule II LeetCode

Question

Currently solving Course Schedule II on LeetCode and this is the code that DOES NOT pass all test cases because of the following line: Collections.reverse(postOrder);. Removing this line solves all test cases.

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        HashMap<Integer, ArrayList<Integer>> 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<Integer> postOrder = new ArrayList<Integer>();

        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<Integer> postOrder, HashMap<Integer, ArrayList<Integer>> 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;
    }
}

I learned that a reverse of post-order DFS produces a valid topological sort. However, when I reverse my DFS post-order list, I get the incorrect answer. I pass all the test cases without the reversal. Does anyone know why this is the case? I appreciate any insights.

This is the main() code for reproducing the incorrect answer:

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

As a result of Test Case 2, the answer my code gives is the reverse of the actual answer.

Answer 1

I learned that a reverse of post-order DFS produces a valid topological sort.

If you reverse a post-order sequence, then you get a pre-order. For example, if you have this (dependency) tree, where a needs b, e and f, ...etc:

         a
       / | \
      b  e  f
     / \   /|\
    c   d g h i

Then the post order sequence is:

c d b e g h i f a

Reversed:

a f i h g e b d c

This means you will now start at the root, and visit the dependencies in the reversed (i.e. wrong) order: a should not be the first in the output, since it is dependent on several other nodes.

Possibly you've heard that you can use a post-order sequence where the children of a node are visited in reversed order. For the example that would be:

i h g f e d c b a

This would work fine.