LeetCode：课程表 (1, 2)

￡神魔★判官ぃ 2021-12-04 01:34 244阅读 0赞

## LeetCode：课程表1 ##

这是很简单的拓扑排序问题

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: \[0,1\]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 
    输出: true
    解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
    输出: false
    解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

来源：力扣（LeetCode）

class Solution {
    public:
        
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            stack<int> S;
            int count = 0;
            vector<int> inDegree(numCourses);
            addEdge(inDegree, prerequisites);
            for(int i = 0; i < numCourses; i ++ )
            {
                if(inDegree[i] == 0)
                    S.push(i);
            }
            while(!S.empty())
            {
                int top = S.top();
                count ++ ;
                S.pop();
                 for(int i=0; i < prerequisites.size(); i++)
                 {
                     if(prerequisites[i][0] == top)
                     {
                        int node = prerequisites[i][1]; 
                        if(!--inDegree[node])
                            S.push(node);
                     }
                 }
            }
            if(count < numCourses)
                return false;
            return true;
        }
        int addEdge( vector<int>& inDegree, vector<vector<int>>& prerequisites){
            for(int i=0; i < prerequisites.size(); i++)
                inDegree[prerequisites[i][1]] ++;
            return 0;
        }
    };

## LeetCode：课程表1 ##

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: \[0,1\]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。  
示例 1:

输入: 2, [[1,0]] 
    输出: [0,1]
    解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
    输出: [0,1,2,3] or [0,2,1,3]
    解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
         因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

来源：力扣（LeetCode）

class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
            int count = 0 ;
            stack<int> S;
            vector<int> res;
            vector<int> inDegree(numCourses);
            addEdge(inDegree, prerequisites);
            for(int i=0; i < numCourses; i ++)
            {
                if(inDegree[i] == 0)
                    S.push(i);
            }
            while(!S.empty())
            {
                int top = S.top();
                res.insert(res.begin(), top);
                S.pop();
                count ++;
                for(int i=0; i < prerequisites.size(); i++)
                {
                    if(prerequisites[i][0] == top)
                    {
                        int node = prerequisites[i][1];
                        if(!--inDegree[node])
                            S.push(node);
                    }
                }
            }
            if( count < numCourses)
            {
                res.clear();
                return res;
            }
            return res;
        } 
        int addEdge(vector<int>& inDegree, vector<vector<int>>& prerequisites)
        {
            for(int i=0; i < prerequisites.size(); i++)
                inDegree[prerequisites[i][1]] ++;
            return 0;
        }
    };