你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
示例 2:
输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
- class Solution {
- public:
- vector<bool> visited;
- vector<bool> path;
- bool res=false;
- bool canFinish(int numCourses, vector
int >>& prerequisites) { - visited.resize(numCourses,false);
- path.resize(numCourses,false);
- vector
int>> graph(numCourses,vector<int>(numCourses,0)); - build(prerequisites,graph);//利用边,创建好邻接矩阵
- for(int i=0;i
//遍历图中的所有节点 - {
- if(!visited[i])//因为图不一定是联通的,可能存在多个子图
- {
- traverse(graph,i);
- }
- }
- return !res;
- }
- void build(vector
int >>& prerequisites,vectorint >>& graph) - {
- for(vector<int> edge:prerequisites)
- {
- int from=edge[1];
- int to=edge[0];
- graph[from][to]=1;
- }
- }
- void traverse(vector
int >>& graph,int i) - {
- if (path[i])
- //成环,就把res置为true,直接返回
- //这个循环判断要写到if(visited[i]){return}前面,不然人家直接return了,就没你什么事了。
- {
- res= true;
- return ;
- }
- if (visited[i])
- {
- return;
- }
- visited[i]=true;
- path[i]=true;
- for(int j=0;j
size();j++) - {
- if(graph[i][j]==1)
- {
- traverse(graph,j);
- }
- }
- path[i]=false;
- }
- };
现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。
例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:
输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
- class Solution {
- public:
- vector<int> path;
- vector<int> visited;
- bool res=false;
- vector<int> postorder;
- vector<int> findOrder(int numCourses, vector
int >>& prerequisites) - {
- vector
int>> graph; - graph.resize(numCourses);
- path.resize(numCourses);
- visited.resize(numCourses);
- build(prerequisites,graph);//根据边,建立邻接表
- for(int i=0;i
//遍历每一个结点 - {
- if(!visited[i]) {
- traverse(graph,i);
- }
- }
- if(res)//如果成环,则不存在拓扑排序,返回空数组
- {
- return vector<int>();
- }
- reverse(postorder.begin(),postorder.end());//后序遍历结果逆序
- return postorder;
- }
- void traverse(vector
int >>& graph,int i) - {
- if(path[i])
- {
- res=true;
- return;
- }
- if(visited[i])
- {
- return ;
- }
- visited[i]=true;
- path[i]=true;
- for(int j:graph[i])
- {
- traverse(graph,j);
- }
- postorder.push_back(i);//把后序遍历的结点添加到数组中
- path[i]=false;
- }
- void build(vector
int >>& prerequisites,vectorint >>& graph) - {
- for(vector<int> edge:prerequisites)
- {
- int from=edge[1];
- int to=edge[0];
- graph[from].push_back(to);
- }
- }
- };
1、构建邻接表。
2、构建一个 indegree
数组记录每个节点的入度。
3、对 BFS 队列进行初始化,将入度为 0 的节点首先装入队列。
4、开始执行 BFS 循环,不断弹出队列中的节点(弹出结点的顺序就是拓扑排序的顺序),减少相邻节点的入度,并将入度变为 0 的节点加入队列。
5、如果最终所有节点都被遍历过(count
等于节点数),则说明不存在环,反之则说明存在环。
- class Solution {
- public:
- queue<int> q;
- bool flag=false;
- vector<int> res;
- vector<int> findOrder(int numCourses, vector
int >>& prerequisites) - {
- vector
int>> graph; - graph.resize(numCourses);
- build(prerequisites,graph);//建立邻接表
- vector<int> indegree;
- indegree.resize(numCourses);
- for(vector<int> edge:prerequisites)//建立indegree数组记录每个结点的入度
- {
- indegree[edge[0]]++;
- }
- bfs(graph,indegree);//广度优先遍历
- if(flag)//不成环,拓扑排序成功
- {
- return res;
- }
- else//成环,返回空容器,无法拓扑排序
- return vector<int>();
- }
- void bfs(vector
int >>& graph,vector<int>& indegree) - {
- for(int i=0;i
size();i++)//先把入度为零的结点入队列 - {
- if(indegree[i]==0)
- {
- q.push(i);
- }
- }
- int count=0;
- while(!q.empty())
- {
- count++;
- int cur=q.front();//弹出队头结点
- res.push_back(cur);
- q.pop();
- for(int j:graph[cur])
- {
- indegree[j]--;//相邻结点入度减一
- if(indegree[j]==0)//如果入度减到0,加入队列中
- {
- q.push(j);
- }
- }
- }
- if(count==indegree.size())//所有结点都入过队列,无环,拓扑排序成功
- {
- flag=true;
- }
- }
- void build(vector
int >>& prerequisites,vectorint >>& graph) - {
- for(vector<int> edge:prerequisites)
- {
- int from=edge[1];
- int to=edge[0];
- graph[from].push_back(to);
- }
- }
- };