LeetCode 207. Course Schedule(拓扑排序

求有向图中是否有环。

法一：拓扑排序

用一个队列维护所有入度为0的节点，每次弹出一个节点v，查看从v可达的所有节点u;

将u的入读减一，若u的入度此时为0, 则将u加入队列。

在队列为空时，检查所有节点的入度，若所有节点入度都为0, 则存在这样的一个拓扑排序 —— 有向图中不存在环。

代码：

class Solution{public:bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites){vector<vector<bool>> map(numCourses, vector<bool>(numCourses, false));vector<int> in_degree(numCourses, 0);for_each(prerequisites.begin(), prerequisites.end(),[&map, &in_degree](pair<int,int> p){if (map[p.first][p.second] == false){map[p.first][p.second] = true;++ in_degree[p.second];}});queue<int> q;for (int id = 0; id < numCourses; ++ id){if (in_degree[id] == 0){q.push(id);}}while (!q.empty()){int course = q.front();q.pop();for (int id = 0; id < numCourses; ++ id){if (map[course][id] == true){– in_degree[id];if (in_degree[id] == 0){q.push(id);}}}}return all_of(in_degree.begin(), in_degree.end(), [](int in) -> bool{return in == 0;});}};

版权声明：本文为博主原创文章，，未经博主允许不得转载。

经历一种身体下了地狱，眼睛进入天堂，灵魂归入故里。