207/210. Course Schedule I/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.

思路: 典型拓扑排序的题目,如果先修课组成的有向图无环,我们可以用拓扑排序找到所有节点。如果有环,则遍历的节点数小于图里总结点数。 拓扑排序的过程:
1. 根据给定的节点建立有向图, 可以用adjacentList来表示。
2. 找到环的入口,即入度(indegree)为0的节点。
3. 用拓扑排序对图进行BFS(需要用个queue)或者DFS(需要用Stack)进行遍历。
以BFS为例, 把indegree为0的点压入queue。count=0初始化并记录遍历过程中的点的个数, BFS的时候先poll出queue中的点,此点做为遍历过的点count++, 对这个点附近的点,循环遍历,每个点的入度-1, 当这个点的入度为0的时候,放入queue,作为下次遍历的点。最后看遍历过点的count跟图中所有点的个数做比较。

复杂度: time O(n) , space O(n)

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses < 0 || prerequisites == null || prerequisites.length == 0) 
            return true;
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        // build graph
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        // find the entrance with indegree == 0
        for (int i = 0; i < graph.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        int cnt = 0;
        while(!queue.isEmpty()) {
            int current = queue.poll();
            cnt++;
            ArrayList<Integer> neighbors = graph[current];
            for (int i = 0; i < neighbors.size(); i++) {
                int neighbor = neighbors.get(i);
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        return cnt == numCourses;
    }
}

Follow up中,要返回课程的修课顺序,我们可以用一个数组来记录就可以。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        int[] order = new int[numCourses];
        // init and build the graph
        for (int i = 0; i < prerequisites.length; i++) {
            if (graph[prerequisites[i][1]] == null) {
                graph[prerequisites[i][1]] = new ArrayList<Integer>();
            }
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        // find entrance
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        // BFS search
        int idx = 0;
        while(!queue.isEmpty()) {
            int current = queue.poll();
            order[idx] = current;
            idx++;
            ArrayList<Integer> neighbors = graph[current];
            if (neighbors == null) continue;
            for (int i = 0; i < neighbors.size(); i++) {
                int neighbor = neighbors.get(i);
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        return idx == numCourses ? order : new int[0];

    }
}

Reference: https://segmentfault.com/a/1190000003814058