207. Course Schedule看不懂这个解法求大神解说

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]
    int[] indegree = new int[numCourses];

    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
//这里不太明白
        if (matrix[pre][ready] == 0)
            indegree[ready]++
        matrix[pre][ready] = 1;
    }

    int count = 0;
    Queue<Integer> queue = new LinkedList();
    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 i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}



补充内容 (2018-7-15 04:51):
   for (int i=0; i<numCourses; i++) {
            if (matrix[course] != 0) { 为什么这里i的范围小于numCourses

这网站上贴 【i】的时候会变成斜体， 然后i也不见了，所以你这个代码不是特别确定到底长什么样。

建议用 gist.github 贴， 方便无公害。

我大概猜一下你的问题。。

首先说他这个方法。 这是bfs做拓扑排序方法， 卡恩方法（kahn's method）。

这个方法原理是说如果任何一个node 的in degree是0，说明他是头。 所以q里面放的就是头。
从头往外的每一个点， 都把头（上一轮）去掉之后，那现在in degree又变成0的话， 说明只能从头进这个点， 那这个点就是下一个头。

举例， 1-2-3-5  2- 4-5. 那么1显然是头。1 去掉之后， 2即头。 2去掉， 3，4均是头。3,4，去掉，5为头。解释的不是特别好， 但我想你大概理解什么意思。。

现在说代码。他这里 indegree[pre][ready] ==0 就是说不想重复计算从pre进入ready的in degree。 因为[pre][ready]如果已经看到过的话 （==1）那么这个in degree不应该再算。

你第二问应该是 if(matrix[courses][j] != 0), 然后 indegree[j]-- 这里是说从你当前的course （头）出来去别的课的indegree 都减1,。如果in degree变0了， 说明这个课变头了。。

这里 j 小于numcourses是因为用的是adj matrix 形式存储， 他不知道从course 到另外哪些课程有没有记录， 所以得全试一遍。

当然你可以不这样记录， 因为假如有6MM课， 但是中间的关系很少的话那matrix就没什么用。。

大概这样。。 o(￣ヘ￣o＃)

the edge is from pre to ready, so degree[ready]++
输入的边如果没有重复复的话， 感觉这个if判断没啥必要，直接++就好了