• Difficulty: Medium

• Related Topics: Depth-first Search, Breadth-first Search, Graph, Topological Sort

• Link: https://leetcode.com/problems/course-schedule/

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
你需要上 numCourses 门课程，每门课程分别从 0 标记为 numCourses-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]
一些课程有前置要求，例如要上课程 0，你就需要先完成课程 1 的学习，在题目中使用像 [0,1] 这样的对表示。

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
给定需要学习的课程总数和一个前置课程列表，判断是否有可能完成所有课程？

Examples

Example 1

Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.

Constraints

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  输入的前置课程列表由边列表表示，而非邻接矩阵。欲了解更多图的表示形式，请点击此处。
• You may assume that there are no duplicate edges in the input prerequisites.
  你可以假定输入中没有重复的边。
• 1 <= numCourses <= 10^5

Hints

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

3. Topological sort could also be done via BFS.

Solution

本题是拓扑排序的一个经典应用了，这里使用的是一个容易理解的拓扑排序的方法：

1. 取出一个入度为 0 的节点，删除该节点及该节点的所有出边

2. 重复 1，直到找不到入度为 0 的节点为止

3. 如果最后图空了，则刚才的遍历顺序为其中一种拓扑排序，否则图中一定存在环路。

具体代码如下（附带详细的注释）

import java.util.*

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        // 邻接矩阵
        val matrix = Array(numCourses) { IntArray(numCourses) }
        // 入度值
        val inDegree = IntArray(numCourses)
        prerequisites.forEach {
            val (ready, pre) = it
            if (matrix[pre][ready] == 0) {
                inDegree[ready]++
            }
            matrix[pre][ready] = 1
        }

        // 构建初始队列，把入度为 0 的节点入队
        val queue: Queue<Int> = ArrayDeque()
        for (i in inDegree.indices) {
            if (inDegree[i] == 0) {
                queue.offer(i)
            }
        }

        // 利用拓扑排序的思想遍历图
        // 具体做法是：找一个入度为 0 的节点，删掉该节点（出队）以及该节点的出边（对应节点的入度 -1）
        // 如果出现新的入度为 0 的节点，加入队列
        // 循环往复，直到队列空了
        var count = 0
        while (queue.isNotEmpty()) {
            val course = queue.poll()
            count++
            for (i in 0 until numCourses) {
                if (matrix[course][i] != 0) {
                    inDegree[i]--
                    if (inDegree[i] == 0) {
                        queue.offer(i)
                    }
                }
            }
        }

        // 最后看遍历到的节点总数和课程总数能不能对得上
        return count == numCourses
    }
}