拓扑排序基础详解，附有练习题

介绍

拓扑排序是一种对有向无环图（DAG）进行排序的算法。在一个有向图中，如果存在一条从节点 A 到节点 B 的路径，那么节点 A 就依赖于节点 B。

有向无环图如下

什么是入度，出度？

入度：有多少个点可以指向该点，例如图中点4，点2和3指向4，故4的入度为2

出度：该点指向多少个点，例如图中点1，指向点2和3，故1的出度为2

求拓扑排序的步骤

1.用vector建图

2.先循环一遍，找到入度为0的点，入队列

3.bfs求拓扑序列。而从队列里弹出的元素x，就是入度为0的点，直接加到ans数组里。

4.接下来要遍历以x为起点，可以到达的点，将这些点的入度减1。如果减1后，入度为0，则将该元素入队列。

5.每循环一次记得判断ans数组的大小有没有超过n，因为总共只有n个元素，如果ans的长度超过了n，说明这是个有向有环图，返回false。否则返回true。

#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include 
#include
#include 
 
#define inf 0x3f3f3f3f
#define int long long
const int N =2e5 + 10;
//#include 
typedef long long ll;
#include
using namespace std;
 
//long long MAX(long long a, long long b) { return a < b ? b : a; }
 
int n, m;
vectorint>> v(1e5 + 10);
int rd[N];//记录每个点的入度
queue<int> q;//如果入度为0，则入列
vector<int> ans;
 
bool topu() {
	for (int i = 1; i <= n; i++) {
		if (!rd[i]) q.push(i);
	}
 
	while (!q.empty()) {
 
		if (ans.size() >= n) break;
 
		int x = q.front();
		q.pop();
		ans.push_back(x);
 
		//遍历x的出度
		for (auto i : v[x]) {
			rd[i]--;
			if (!rd[i]) q.push(i);
		}
 
	}
	return ans.size() == n;
}
signed main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		rd[b]++;
	}
 
 
	if (topu()) {
		for (int i = 0; i < n; i++) {
			if (i == 0) cout << ans[i];
			else cout << " " << ans[i];
		}
	}
	else cout << -1 << endl;
 
	return 0;
}