LeetCode - Course Schedule 解题报告

以前从来没有写过解题报告，只是看到大肥羊河delta写过不少。最近想把写博客的节奏给带起来，所以就挑一个比较容易的题目练练手。

原题链接

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

题目大意

有n个课程，编号分别是0到n－1。我们的目标是修完所有课程。然而有些课程有前置课程的，我们必须修完前置课程才能修该门课程。题目给了我们课程之间的前置关系，让我们判断是否能修完所有课程。

题目原型

这个题目的描述简单粗暴，我们不难发现，其实是给了我们一个有向图，然后问我们这个图里面是否存在环。

解题思路

我们的目的也非常直观，就是判断一个有向图是否存在环。

我想到的是用dfs。首先构造出一棵树（当然不一定是真正的树，因为有可能存在环；也有可能是多棵树）。然后对每棵树进行深搜，一旦发现某个节点和它的祖先节点相同，就存在环。这里给出一份伪代码。其中processed状态并不是必须的，只是为了避免一些不必要的重复搜索。

// 伪代码
foreach node
{
    if (node is not processed)
        dfs(node);
}

dfs(node)
{
    mark node as processed
    mark node as visiting
    foreach childNode
    {
        if (node is visiting)
        {
            find circle and stop;
        }
        if (childNode is not processed)
        {
            dfs(childNode)
        }
    }
    mark node as not visiting
}

不过我最后并没有用这种方法，而是用了一个叫做Kahn的拓扑排序典型算法。让我来介绍一下这个算法的流程（其实很简单，一看包会）。

// L 储存最终有序结果的List
// S 储存所有不存在入边的节点，即入度为0的点的集合
while S is not empty
    get a node x from S
    append x to list L
    foreach node that has an edge from x(e.g. x -> y)
        remove that edge
        if y doesn't contain any income edges
            add y to set S

if L contains all the nodes
    succeed
else
    fail

这个算法的精髓在于维护了一个入度为0的点的集合（这个集合可以是set，array，list等，非常*），每次处理掉一个0入度的点，然后把新产生的0入度的点添加到该集合。

结合我们的题目，可以发现这个算法可以直接应用到我们这个题上来，而不需要任何的额外改变。所以我就直接贴代码了。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 个人习惯，判断一下特殊情况
    if (numCourses <= 1 || prerequisites == null)
    {
        return true;
    }
    Stack<Integer> out[] = new Stack[numCourses]; // 所有的边
    for (int i = 0; i < numCourses; i++)
    {
        out[i] = new Stack<Integer>();
    }

    int[] in = new int[numCourses]; // 统计入度的数组
    for (int i = 0; i < prerequisites.length; i++)
    {
        out[prerequisites[i][0]].push(prerequisites[i][1]);
        in[prerequisites[i][1]]++;
    }

    Stack<Integer> noneIn = new Stack<Integer>(); // 集合S
    int res = 0;  // 由于并不需要最终的排序结果，所以只记录了L中的个数

    for (int i = 0; i < numCourses; i++)
    {
        if (in[i] == 0)
        {
            noneIn.push(i);
        }
    }

    while (!noneIn.isEmpty())
    {
        int x = noneIn.pop();
        res++;
        while (!out[x].isEmpty())
        {
            int y = out[x].pop();
            if (--in[y] == 0)
            {
                noneIn.push(y);
            }
        }
    }

    return res == numCourses;
}