对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v> ∈ E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
有向图的拓扑序列
给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m。接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出-1。
数据范围
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
- 一个有向无环图，一定至少存在一个入度为0的点
- 使用BFS思想：开始让所有入度为0的点入队，在循环过程中，枚举队头元素的所有出边，删掉队头元素（枚举的元素入度减1），如果这些元素入度为0，则加入到队列中，这样不断循环
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
// 记录每个点的入度
int d[N];
// 记录拓扑排序
vector<int> res;
vector<int> g[N];
bool topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
q.push(i);
res.push_back(i);
}
}
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 0; i < g[t].size(); i++) {
int j = g[t][i];
d[j]--;
if (d[j] == 0) {
q.push(j);
res.push_back(j);
}
}
}
// 如果有环则说明一定没有加到队列中来
return res.size() == n;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++ ) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
d[b]++;
}
if (!topsort())
cout << "-1" << endl;
else {
for (int i = 0; i < res.size(); i++)
cout << res[i] << ' ';
cout << endl;
}
return 0;
}
判断拓扑排序序列
输入格式
第一行包含两个整数 N 和 M，分别表示有向图的点和边的数量。接下来 M 行，每行给出一条边的起点和终点。点的编号从 1 到 N。再一行包含一个整数 K，表示询问次数。接下来 K 行，每行包含一个所有点的排列。一行中的数字用空格隔开。
输出格式
在一行中输出所有不是拓扑序列的询问序列的编号。询问序列编号从 0 开始。行首和行尾不得有多余空格，保证存在至少一个解。
数据范围
输入样例：
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
输出样例：
3 4
- 使用数组存储序列下标
- 枚举每条边：判断起点下标是否都小于终点下标
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010, M = 10010;
struct Edge {
int a;
int b;
} e[M];
int n, m;
// 记录路径中的下标
int pos[N];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
e[i].a = a;
e[i].b = b;
}
int k;
cin >> k;
vector<int> res;
for (int i = 0; i < k; i++) {
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
pos[x] = j;
}
bool success = true;
for (int j = 0; j < m; j++) {
if (pos[e[j].b] < pos[e[j].a]) {
success = false;
break;
}
}
if (!success)
res.push_back(i);
}
if (res.size() > 0) {
cout << res[0];
for (int i = 1; i < res.size(); i++)
cout << ' ' << res[i];
}
return 0;
}
