行业网站设计公司_注册电商平台需要什么手续_百度竞价推广专员_社交网络推广方法

AC截图

题目

思路

这道题可以抽象为一个有向无环图，判断是否可以进行拓扑排序

①构建邻接表

vector<vector<int>> edge：下标代表节点编号，数组内容代表该结点的直接后置结点

vector<int> indegree：下标代表结点编号，数组内容代表该结点入度。在入度为0的时候，可以加入拓扑排序序列。

②将所有入度为0的结点加入队列

③进行bfs遍历

代码

class Solution {
public:vector<vector<int>> edge;vector<int> indegree;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edge.resize(numCourses);indegree.resize(numCourses);for(auto pre:prerequisites){edge[pre[1]].push_back(pre[0]);indegree[pre[0]]++;}queue<int> q;for(int i=0;i<numCourses;i++){if(indegree[i]==0){q.push(i);}}int visit=0;while(!q.empty()){visit++;int u = q.front();q.pop();for(int v:edge[u]){indegree[v]--;if(indegree[v]==0){q.push(v);}}}return visit==numCourses;}
};