Course schedule I and II

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

The first problem requires us to find if there is a cycle in the graph, if there is, then its a false. It does not require topological sort, yet if you use traditional DFS, it will exceed time limit. However, we can do a little bit optimization to avoid traverse already traversed path. Instead of using a boolean to track visited nodes, we can use an int array. For visited node, we mark it as 1, for the node that is visited and the path that is rooted by it does not contain cycle, we mark it as 2. So along any path if we find a node that is marked as 2, we can save our time and return "true" directly.

 public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites == null || prerequisites.length == 0)
            return true;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prequisit : prerequisites) {
            int klass = prequisit[0];
            if (!map.containsKey(prequisit[0]))
                map.put(klass, new ArrayList<>());
            map.get(klass).add(prequisit[1]);
        }
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!helper(visited, map, i))
                return false;
        }
        return true;
    }
    
    private boolean helper(int[] visited, Map <Integer, List<Integer>> map, int i) {
        visited[i] = 1;
        //no prerequisit
        if (!map.containsKey(i)) {
            visited[i] = 2;
            return true;
        }
        for (int pre : map.get(i)) {
            if (visited[pre] == 2)
                break;
            if (visited[pre] == 1 || !helper(visited, map, pre))
                return false;
        }
        visited[i] = 2;
        return true;
    } 

The second problem, on the other hand, requires topological sort. Common approach to it is to first find all vertices with indegree 0. Then for each vertex with indegree 0, remove all its neighbor nodes. Iteratively perform this process until all nodes are found.

 public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new HashSet<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] indegrees = new int[numCourses];
        for (Set<Integer> pre : adjList) {
            for (int i : pre)
                indegrees[i]++;
        }
        Queue<Integer> first = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0)
                first.add(i);
        }
        int[] rst = new int[numCourses];
        int count = 0;
        while (!first.isEmpty()) {
            int curr = first.poll();
            for (int i : adjList.get(curr)) {
                indegrees[i]--;
                if (indegrees[i] == 0)
                    first.add(i);
            }
            rst[count++] = curr;
        }
        return count == numCourses ? rst : new int[]{};
    }

I was considering using DFS for the problem. However, traditional DFS for topological sort requires DAG, which cannot be guaranteed by this problem.