207. Course Schedule & 210. Course Schedule II

Published on April 19, 2023

Question

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Algorithm

This is a typical question utilizing topological sorting. A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

A topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

The detailed algorithm pseudo code could be found on Wiki. I'd list the implementation of DFS and BFS with comments.

Code

207

This question doesn't require you to have the result list, you only need to return if it can finish(no cycle). If you do question 210 first, this question would be easy.We just check if the result traverse all the elements, which compare length of result set and number of course.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            indegrees[prerequisite[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int course = queue.poll();
            for (int[] prerequisite : prerequisites) {
                if (course == prerequisite[1]) {
                    indegrees[prerequisite[0]]--;
                    if (indegrees[prerequisite[0]] == 0) {
                        queue.offer(prerequisite[0]);
                    }
                }
            } 
        }

        for (int indegree : indegrees) {
            if (indegree != 0) {
                return false;
            }
        }
        return true;
    }
}

210

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        int[] res = new int[numCourses];
        int k = 0;
        for (int[] prerequisite : prerequisites) {
            indegrees[prerequisite[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
                res[k++] = i;
            }
        }

        while (!queue.isEmpty()) {
            int course = queue.poll();
            for (int[] prerequisite : prerequisites) {
                if (course == prerequisite[1]) {
                    indegrees[prerequisite[0]]--;
                    if (indegrees[prerequisite[0]] == 0) {
                        queue.offer(prerequisite[0]);
                        res[k++] = prerequisite[0];
                    }
                }
            } 
        }
        return k == numCourses ? res : new int[0];
    }
}

DFS Implementation

package Graph.topologicalSort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by szhang on 2023/4/19
 */
public class DFSImplementation {

    public static void main(String[] args) {
        int[][] prerequisites = new int[1][1];
        prerequisites[0] = new int[]{0, 1};
        int numOfCourses = 2;
        int[] res = findRes(prerequisites, numOfCourses);
        for (int i: res
        ) {
            System.out.println(i);
        }
    }

    public static int[] findRes(int[][] prerequisites, int numOfCourses) {
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> graph = new ArrayList<>();
        // build graph
        for (int i = 0; i < numOfCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] prerequisite: prerequisites) {
            graph.get(prerequisite[0]).add(prerequisite[1]);
        }
        // build visit status, 0:unvisited, 1:visiting, 2:visited
        Map<Integer, Integer> visit = new HashMap<>();
        // mark all node unvisited;
        for (int i = 0; i < numOfCourses; i++) {
            visit.put(i, 0);
        }

        //
        for (int i = 0; i < numOfCourses; i++) {
            if (visit.get(i) != 2) { // if the node is unvisited, check if there is cycle start dfs from it
                if (hasCycle(res, graph, i, visit)) {
                    return new int[]{}; // has cycle, return empty array;
                }
            }
        }

        // the node in dfs is added in reverse order, so the output should be reversely out put to get the right order
        int[] ret = new int[numOfCourses];
        int index = 0;
        for (int i = 0; i < res.size(); i++) {
            ret[index++] = res.get(res.size() - 1 - i);
        }

        return ret;
    }

    private static boolean hasCycle(List<Integer> res, List<List<Integer>> graph, int i, Map<Integer, Integer> visit) {
        if (visit.get(i) == 2) { // node has been visited
            return false;
        } else if (visit.get(i) == 1) { // node is being visiting
            return true;
        }
        visit.put(i, 1);
        for (int j = 0; j < graph.get(i).size(); j++) {
            hasCycle(res, graph, graph.get(i).get(j), visit);
        }
        visit.put(i, 2);
        res.add(i);
        return false;
    }
}