Course Schedule解题报告

Description:

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?

Example:

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.

Link:

解题方法：

用DFS：
如果检查到图中有环，则返回false，但是这个方法比较慢；

用BFS：
针对每个结点，我们要储存其入度，从入度为0的结点开始进行搜索；
为了应对一门课程有几个前置课程的情况，每次搜索到下一个结点时，对其入度减一，当一个结点的入度为0时，才能加入到队列中。当一个图有环的时候，因为入度不可能为0，所以永远不会进入这个环当中。
最后比较我们搜索到的点和课程总数是否一致。

Time Complexity：

DFS: O(n*e) n为节点数，e为边数
BFS: O(n)

完整代码：

DFS

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) 
    {
        vector<vector<int>> hash(numCourses);
        for(auto a: prerequisites)
            hash[a.first].push_back(a.second);
        bool complete = true;
        unordered_set<int> visited;
        for(int i = 0; i < numCourses; i++)
        {
            visited.insert(i);
            helper(i, visited, complete, hash);
            visited.erase(i);
        }
        return complete;
    }
    void helper(int curr, unordered_set<int> &visited, bool &complete, vector<vector<int>> &hash)
    {
        if(!complete || hash[curr].empty())
            return;
        for(int i = 0; i < hash[curr].size(); i++)
        {
            if(visited.find(hash[curr][i]) != visited.end())
            {
                complete = false;
                return;
            }
            visited.insert(hash[curr][i]);
            helper(hash[curr][i], visited, complete, hash);
            visited.erase(hash[curr][i]);
        }
    }

BFS

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) 
    {
        vector<vector<int>> hash(numCourses);
        vector<int> idg(numCourses);
        for(auto a: prerequisites)
        {
            hash[a.second].push_back(a.first);
            idg[a.first]++;
        }
        queue<int> Q;
        unordered_set<int> taken;
        for(int i = 0; i < numCourses; i++)
        {
            if(idg[i] == 0)
                Q.push(i);
        }
        while(!Q.empty())
        {
            int curr = Q.front();
            cout<<curr<<endl;
            Q.pop();
            if(taken.find(curr) != taken.end())
                return false;
            taken.insert(curr);
            for(int i = 0; i < hash[curr].size(); i++)
            {
                idg[hash[curr][i]]--;
                if(idg[hash[curr][i]] == 0)
                    Q.push(hash[curr][i]);
            }  
        }
        return taken.size() == numCourses;
    }