拓扑排序（c++）

拓扑排序：可以对有向图的数据按照先后顺序进行排序，也可以用来检测有向图中有没有环

题目

课程表

题目描述

你这个学期必须选修n门课程，记为0到n-1。在选修某些课程之前需要一些先修课程。给你一个数组p，其中p[i]=[ai,bi]表示如果想选修课程ai，则必须先选修课程bi。m表示数组p中数据个数

例如，想要学习课程0，你需要先完成课程1，我们用一个匹配来表示:[0,1]。

先输入n、m，再输入数组p。
请你判断是否可能完成所有课程的学习?如果可以，返回true;否则,返回false。

样例

输入：

2 2

1 0

0 1

输出

false

解释:课程1需要先学0，课程0又需要先学1，存在循环依赖，不可能完成。

代码

#include <bits/stdc++.h> using namespace std; int a[1010][1010];//邻接矩阵 int c[1010];//入度 int b[1010];//是否被访问 int r[1010];//排序结果 int lr; int n,m; queue<int> q; void bfs(); int main() { cin>>n>>m; for(int i = 0;i<m;i++) { int x,y; cin>>x>>y; a[y][x] = 1;//构建邻接矩阵 c[x]++;//增加入度的数量 } bfs(); if(lr==n) cout<<"true"; else cout<<"false"; return 0; } void bfs() { for(int i = 0;i<n;i++) { if(c[i]==0)//入度等于0 { q.push(i); b[i] = 1;//标记已被访问 r[lr] = i;//排序 lr++; } } while(q.empty()==false) { int head = q.front(); q.pop(); for(int i = 0;i<n;i++) { if(a[head][i]==1&&b[i]==0) { c[i]--; if(c[i]==0) { q.push(i); b[i] = 1;//标记已被访问 r[lr] = i;//排序 lr++; } } } } }

课程表二

题目描述

现在你总共有n门课，编号为0到n-1。给你一个数组p，其中p[i=[ai,bi表示如果你想选修课程ai，则必须先完成课程bi。例如，[0,1]表示要选修课程0，必须先选修课程1。返回一种修完所有课程的顺序(可能存在多种有效顺序，你只需要返回其中一种)。如果不可能完成所有课程，返回一个空数组。m表示数组p中数据个数。

先输入n、m，再输入数组p。

样例

输入

4 4

1 0

2 0

3 1

3 2

输出

0 1 2 3

（0 2 1 3 也可以）

代码

#include <bits/stdc++.h> using namespace std; int a[1010][1010];//邻接矩阵 int c[1010];//入度 int b[1010];//是否被访问 int r[1010];//排序结果 int lr; int n,m; queue<int> q; void bfs(); int main() { cin>>n>>m; for(int i = 0;i<m;i++) { int x,y; cin>>x>>y; a[y][x] = 1;//构建邻接矩阵 c[x]++;//增加入度的数量 } bfs(); if(lr==n) { for(int i = 0;i<lr;i++) { cout<<r[i]<<" "; } } else { cout<<0; } return 0; } void bfs() { for(int i = 0;i<n;i++) { if(c[i]==0)//入度等于0 { q.push(i); b[i] = 1;//标记已被访问 r[lr] = i;//排序 lr++; } } while(q.empty()==false) { int head = q.front(); q.pop(); for(int i = 0;i<n;i++) { if(a[head][i]==1&&b[i]==0) { c[i]--; if(c[i]==0) { q.push(i); b[i] = 1;//标记已被访问 r[lr] = i;//排序 lr++; } } } } }