leetcode201拓扑排序 （C++ 实现）

本文主要是介绍leetcode201拓扑排序 （C++ 实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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?

输入

2, [[1,0]]

输出

true

Explanation:

There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

题目分析

本题实质上是一个拓扑排序，拓扑排序属于数据结构有向图中的具体内容，构建有向图的方法有很多，这里我们使用vector<list> 邻接链表来构造有向图，实现上访问的时间复杂度比邻接矩阵要低。同时拓扑排序的核心是利用一个队列存储入度为零的节点，每次取出一个入度为零的节点然后将它作为入度的定点减一。拓扑排序的时间复杂度为O(m+n),其中n为点的个数，m为边的个数。

详细代码

class Solution {
public:bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {list<int> l;vector<list<int>> grph(numCourses, l);vector<int> degree(numCourses, 0);pair<int, int> p;for(int i = 0; i < prerequisites.size(); ++i){p = prerequisites[i];degree[p.second]++;//记录节点的入度grph[p.first].push_back(p.second);//建立邻接矩阵}queue<int> q;//拓扑排序for(int i = 0; i < numCourses; ++i){//注意 此处判断的条件是节点的个数if(!degree[i]){q.push(i);}}while(!q.empty()){int t = q.front();q.pop();list<int> k = grph[t];list<int> :: iterator it = k.begin();for(; it != k.end(); ++it){degree[*it]--;if(degree[*it] == 0){q.push(*it);}}}for(int i = 0; i < numCourses; ++i){if(degree[i] > 0){return false;}}return true;}
};

这篇关于leetcode201拓扑排序 （C++ 实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---