Question

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.

Code

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] degree = new int[numCourses];
        int m = prerequisites.length;
        for (int i = 0; i < m ; i++) {
            degree[prerequisites[i][1]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0 ; i < numCourses; i++) {
            if (degree[i] == 0) queue.add(i);
        }
        
        int count = queue.size();
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int i = 0; i < m; i++) {
                if (x == prerequisites[i][0]) {
                    int y = prerequisites[i][1];
                    degree[y]--;
                    if (degree[y] == 0) {
                        queue.offer(y);
                        count++;
                    }
                }
            }
        }
        return count == numCourses;
    }
}

Solution

使用拓扑排序。

拓扑排序，其实就是寻找一个入度为0的顶点，该顶点是拓扑排序中的第一个顶点序列，将之标记删除，然后将与该顶点相邻接的顶点的入度减1，再继续寻找入度为0的顶点，直至所有的顶点都已经标记删除或者图中有环。

从上可以看出，关键是寻找入度为0的顶点。

一种方式是遍历整个图中的顶点，找出入度为0的顶点，然后标记删除该顶点，更新相关顶点的入度，由于图中有V个顶点，每次找出入度为0的顶点后会更新相关顶点的入度，因此下一次又要重新扫描图中所有的顶点。故时间复杂度为O(V^2)

由于删除入度为0的顶点时，只会更新与它邻接的顶点的入度，即只会影响与之邻接的顶点。但是上面的方式却遍历了图中所有的顶点的入度。

改进的另一种方式是：先将入度为0的顶点放在栈或者队列中。当队列不空时，删除一个顶点v，然后更新与顶点v邻接的顶点的入度。只要有一个顶点的入度降为0，则将之入队列。此时，拓扑排序就是顶点出队的顺序。该算法的时间复杂度为O（V+E）。

第一步：遍历图中所有的顶点，将入度为0的顶点 入队列。

第二步：从队列中出一个顶点，打印顶点，更新该顶点的邻接点的入度(减1)，如果邻接点的入度减1之后变成了0，则将该邻接点入队列。

第三步：一直执行上面 第二步，直到队列为空。