拓扑排序

207.课程表

[1,0]表示0->1

数据结构：

• 入度表 vector<int>

• 邻接表 map<int,vector<int>>

• 队列 queue<int> 存储入度为0的结点

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        /*
        1->2
        1->3
        得到1->2,3
        将1弹出时，2的入度和3的入度--
        */
        vector<int> inDegree(numCourses);
        map<int,vector<int>> map;
        for(int i=0; i<prerequisites.size(); i++)
        {
            inDegree[prerequisites[i][0]]++;
            map[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        queue<int> que;
        for(int i=0; i<numCourses; i++)
        {
            if(inDegree[i]==0) que.push(i);
        }
        int count=0;
        while(que.size())
        {
            int selected=que.front();//当前选的课
            que.pop();
            count++;
            vector<int> next_course=map[selected];//后序课
            for(int i=0; i<next_course.size(); i++)
            {
                inDegree[next_course[i]]--;
                if(inDegree[next_course[i]]==0) que.push(next_course[i]);
            }
        }
        return count==numCourses;
    }
};