7ms simple Java solution


  • 0
    Y
    public class Solution {
        enum Status {
            NEW,
            VISITING,
            VISITED
        }
        List<List<Integer>> adj;
        int[] res;
        Status[] visited;
        int rc;
        boolean cycle = false;
        
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            res = new int[numCourses];
            rc = 0;
            if (numCourses == 0) return res;
            visited = new Status[numCourses];
            buildAdjacencyList(numCourses, prerequisites);
            for (int i = 0; i < numCourses; i++) topoSort(i);
            return cycle ? new int[0] : res;
        }
        
        void topoSort(int cur) {
            if (visited[cur] == Status.VISITED || cycle) return;
            if (visited[cur] == Status.VISITING) {
                cycle = true;
                return;
            }
            visited[cur] = Status.VISITING;
            for (int i = 0; i < adj.get(cur).size(); i++) {
                if (cycle) return;
                topoSort(adj.get(cur).get(i));
            }
            res[rc++] = cur;
            visited[cur] = Status.VISITED;
        }
        
        void buildAdjacencyList(int numCourses, int[][] prerequisites) {
            adj = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                adj.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.