207. Course Schedule

yPhantom 2019年10月14日 28次浏览

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?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.

Solution

参考wiki拓扑排序,将这些课程都看成一个一个的节点,组成有向图,由先修课指向需要先修的课程。那么入度为0的节点代表着不需要任何先修课。

因此,如果我们先删掉入度为0的节点,及其相关的边(理解成我们已经先修了这几门课程,此时我们修了的课程数等于第一轮删掉的入度为0的节点的个数)。此时又会有一些点的入度变成0,重复前一步的操作,知道最后,如果不剩下边了,代表着这个图是可以解的(符合拓扑排序的),代表着没有环。

当然,如果我们在解这个有向图解到最后,还剩下边,但是已经删掉的节点数大于或者等于题目中给的hava to take的课,那么也是可以的。

附上代码:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] neigh = new LinkedList[numCourses]; // 链表数组,neigh[0]代表需要课程0作为先修课的有哪些
        Queue<Integer> queue = new LinkedList<>(); // 作为存放入度为0节点的队列,起后面的循环作用
        int[] indegree = new int[numCourses]; // indegree[0]代表课程0的入度
        int count = 0;
        for (int i = 0; i< neigh.length; i++) {
            neigh[i] = new LinkedList<>(); // 初始化每个链表
        }
        for(int[] pair: prerequisites) {
            neigh[pair[1]].add(pair[0]); // 以pair[1]为先修课的链表中应当加入pair[0]
            indegree[pair[0]]++; // 有向图由pair[1]指向pair[0],pair[0]入度+1
        }
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for(int adj: neigh[course]) {
                if(--indegree[adj] == 0) {
                    queue.offer(adj);
                }
            }
        }
        return count >= numCourses; // 删除的节点数量大于必须要修的课程数即可
    }
}