LeetCode Course Schedule

· 639 words · 2 minute read
2017年8月
LeetCode

207. Course Schedule

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.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

方法

先普及一下什么是拓扑排序？

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 ∈E(G)，则u在线性序列中出现在v之前。

通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。

对于本题，若存在环则排序失败。解题流程如下：

  1. 对于有入度的节点，计算每个节点的入度值，计算完后找到入度为0的节点加入队列，若队列不为空则跳到2，若队列为空则跳到3.
  2. 在队列中找到入度为0的点的下一个节点，并将下一个节点的入度减一，即删除入度0的节点到下一个节点的边，若这下一个节点的入度为0，则加入队列，如此循环反复。举例 1 -> 2 -> 3 .

  3. 若队列为空，或者经过2跳到3，那么判断所有节点的入度是否为0，若都为0，则返回true，否则返回false.

    public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses == 0 || prerequisites.length == 0){
            return true;
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] inDegree = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){
            inDegree[prerequisites[i][0]]++;
        }
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                queue.add(i);
            }
        }
        while(queue.size() != 0){
            int n = queue.poll();
            for(int i = 0; i < prerequisites.length; i++){
                if(prerequisites[i][1] == n){
                    inDegree[prerequisites[i][0]]--;
                    if(inDegree[prerequisites[i][0]] == 0){
                        queue.add(prerequisites[i][0]);
                    }
                }

            }
        }
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] != 0){
                return false;
            }
        }
        return true;
    }
}
Share