拓扑排序模板题
思路
见: https://leetcode-cn.com/problems/course-schedule/solution/rang-ni-miao-dong-de-bao-mu-ji-tuo-bu-pa-o4b1/
需要一个维护每个点入度的数组,一个邻接表,和一个存放入度为0的点的队列
代码
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int n=prerequisites.size();
if(!n) return true;
vector<int> indegree(numCourses,0);//记录每个点的入度
vector<vector<int>> adj(numCourses);//邻接表
queue<int> q;//辅助队列
for(int i=0;i<n;i++)//统计每个点的入度,并且构建邻接表
{
indegree[prerequisites[i][0]]++;
adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
for(int i=0;i<numCourses;i++)//将入度为0的点入队
if(!indegree[i])
q.push(i);
int count=0;//已修课程数量
while(!q.empty())
{
int x=q.front();
count++;
q.pop();
for(int i=0;i<adj[x].size();i++)//删掉该点后,把这个课程所指向的所有点的入度都减1
{
indegree[adj[x][i]]--;
if(!indegree[adj[x][i]])//如果出现了入度为0的情况就将该点入队
q.push(adj[x][i]);
}
}
if(count==numCourses)//如果修的课程数量等于numCourses
return true;
return false;
}
};
厉害~ ~