LeetCode#207: Course Schedule

Problem

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.
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.

题意

现在总共有n门要上的课，编号从0到n - 1。
有些课必须先上一些前置课程才能上，比如说要上编号为0的课，必须先完成编号为1的课程才行，这样的关系被表示为一个pair：[0, 1]。
给出课程总数n和一个pair的表，判断是否有可能完成所有的课程？

分析

这个题本质上是一个判断一张图是否为有向无环图（DAG）的题目。

DAG，顾名思义，如果一个有向图中从任意点出发都不能回到该点的话，这张图就是一个有向无环图
课程就表示图中的点，而前置课程的关系则表示了图中的有向边。需要特别注意的是，完成事件A才能继续完成事件B，这样的关系我们通常表示为A->B；但是在题目中，要先完成课程1才能完成课程0，这个关系被表示为了[0, 1]，所以在代码中构造图的信息时，需要留意。

根据《算法概论》中对有向无环图的讲解，判断一个有向图是否有环，有两个算法：

1. 拓扑排序
   即找出该图的一个线性序列，使得需要事先完成的事件总排在之后才能完成的事件之前。如果能找到这样一个线性序列，则该图是一个有向无环图

2. DFS
   遍历图中的所有点，从i点出发开始DFS，如果在DFS的不断深入过程中又回到了该点，则说明图中存在回路。

对这道题，自己没有得到很好的解法，代码也不是很优雅，所以主要以Leetcode上Solution中的C++代码为例，看看是如何实现这两种算法的。

Code

拓扑排序

/*******************************************/
/* 类拓扑排序算法的实现
/* 说明：
/*      由于题目只要求判断是否存在环，并不需要直接给出线性序列解
/*      所以代码只是用了拓扑排序的思想，而不是真正实现了拓扑排序
/* 实现思路：
/*      每次从图中去掉一个入度为0的点，去掉该点后，该点指向的点的入度-1；
/*      如果最后所有的点都被去掉了，则说明该图是dag
/* 步骤：
/*      1. 建立一个二维出表，存放了每个点指向的点
/*      2. 初始化得到每个点的入度
/*      3. for循环次数为n次，每次遍历整个出表，如果没有找到入度为0的点则return false；否
/*         则记录j，将j的入度标为-1，防止重复访问该点
/*      4. 将j点指向的点的入度全部减一
/*      5. 开始新的循环
/*******************************************/
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        _iniInDegree(numCourses, prerequisites);
        _iniOutTable(numCourses, prerequisites);
        for (int i = 0; i < numCourses; i++){
            int j = 0;
            for (; j < numCourses; j++){
                if (inDegree[j] == 0)   break;
            }
            if (j == numCourses)    return false;
            inDegree[j] = -1;
            for (int k = 0; k < outTable[j].size(); k++)
                inDegree[outTable[j][k]]--;
        }
        return true;
    }
private:
    vector<int> inDegree;
    vector<vector<int>> outTable;
    void _iniInDegree(int numCourses, vector<pair<int, int>>& prerequisites){
        inDegree.resize(numCourses);
        for (int i = 0; i < numCourses; i++)
            inDegree[i] = 0;
        for (int i = 0; i < prerequisites.size(); i++)
            inDegree[prerequisites[i].first]++;
    } 
    void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
        outTable.resize(numCourses);
        for (int i = 0; i < prerequisites.size(); i++)
            outTable[prerequisites[i].second].push_back(prerequisites[i].first);
    }
};

DFS

/*******************************************/
/* DFS算法的实现
/* 说明：
/*      从一点开始进行DFS，如果在DFS深入的过程中又回到了该点，则该图存在环路；否则该图是DAG
/* 步骤：
/*      1. 同上
/*      2. 建立两个bool容器visited和onpath，大小均为numCourses，初始值均为false
/*      3. visited标记被访问过的点；onpath标记某个点当前是否正在被dfs
/*      4. for循环次数为n次，每次判断一个点：
/*         如果该点未被访问过，则对该点进行DFS（用&&来实现）
/*         如果该点DFS的结果为true，表明从这一个点出发得到了环路（取决于DFS的返回值设定，也可以设定为false），return false
/*         如果该点DFS的结果为false，则表明没有在该点探测到环路，return true
/*      5. DFS函数的结构
/*         先判断当前dfs的点是否被访问过了，如果被访问过，return false
/*         如果没有被访问过，那么将该点的visited和onpath置为true
/*         遍历该点指向的点，如果有一点正在被dfs（onpath为true），则表明存在环路，返回true；如果没有，则对该点进行dfs
/* Note：不要把多线程的概念混进来，对于DFS而言，任意时刻只有一棵DFS树在生长，只有当这棵树被完全return了之后才会进行下一轮的DFS
/*******************************************/
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        _iniOutTable(numCourses, prerequisites);
        visited.resize(numCourses);
        onpath.resize(numCourses);
        for (int i = 0; i < numCourses; i++)
            visited[i] = onpath[i] = false;
        
        for (int i = 0; i < numCourses; i++){
            /* 在C++中，进行与运算时，如果第一个表达式的值是false，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
            if (!visited[i] && _dfs(i))
                return false;
        }
        return true;
    }
private:
    vector<vector<int>> outTable;
    vector<bool> visited;
    vector<bool> onpath;
    void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
        outTable.resize(numCourses);
        for (int i = 0; i < prerequisites.size(); i++)
            outTable[prerequisites[i].second].push_back(prerequisites[i].first);
    }
    bool _dfs(int v){
        if (visited[v]) return false;
        visited[v] = onpath[v] = true;
        for (int i = 0; i < outTable[v].size(); i++){
            /* 在C++中，进行或运算时，如果第一个表达式的值是true，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
            if (onpath[outTable[v][i]] || _dfs(outTable[v][i]))
                return true;
        }
        /* return false */
        return onpath[v] = false;
    }
};