拓扑排序食用方式

首先我们要知道什么是拓扑排序，在介绍这一概念之前，我们首先要认识一下什么叫入度和出度。

入度：是指一个点被多少条边指向。

出度：是指着一个点出去了多少边。

通俗点理解拓扑排序就是，只有从前指向后边的点，没有从后边指向前边的边。

拓扑排序就是要将入度为零的点放入队列，然后删去该点，指向的所有边，入队的顺序就是拓扑排序。

因此我们可以推断，只要没有自环，一定存在拓扑排序，如果有自环，一定有拓扑排序。

另外还需要注意，拓扑排序也不是唯一的。

给定一个 nn 个点 mm 条边的有向图，点的编号是 11 到 nn，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1−1。

若一个由图中所有点构成的序列 AA 满足：对于图中的每条边 (x,y)(x,y)，xx 在 AA 中都出现在 yy 之前，则称 AA 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 mm 行，每行包含两个整数 xx 和 yy，表示存在一条从点 xx 到点 yy 的有向边 (x,y)(x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1−1。

数据范围

1≤n,m≤105   1≤n,m≤105

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

代码如下：

 
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
const int N = 1e05 + 10, M = N * 2;
 
int read(){
	int res = 0 , flag = 1 ;
	char c = getchar() ;
	while(!isdigit(c)){
		if(c == '-') flag = -1 ;
		c = getchar() ;
	}
	while(isdigit(c)){
		res = (res << 1) + (res << 3) + (c ^ 48) ;
		c = getchar() ;
	}
	return res * flag ; 
}
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];
 
void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++;
}
 
bool topsort() {
	int tt = -1, hh = 0;
	for (int i = 1; i < n; i++) {
		if(!d[i]) {
			q[++tt] = i; 
		}
	}
 
	while (hh <= tt) {
		auto u = q[hh++];
		for (int i = h[u]; i != -1; i = ne[i]) {
			int j = e[i];
			if (--d[j] == 0) {
				q[++tt] = j;
			}
		}
	}
 
	return tt == n - 1;
}
int main()  {
	memset(h, -1, sizeof h);
	n = read();
	m = read();
	while (m --) {
		int a, b;
		a = read();
		b = read();
		add(a, b);
		d[b] ++;
	}
 
	if (topsort()) {
		for (int i = 0; i < n; i++) {
			cout << q[i] << ' ';
		}
	} else {
		puts("-1");
	}
 
	return 0;
}