拓扑排序

拓扑排序实现（手写队列牛b！！！）

（但我还是更喜欢queue。。。）

int ind[MAXN];
int d[MAXN];
int q[MAXN], qhead = 0, qtail = 0;

void topo() {
for (int i = 1; i <= n; i++) {
if (!ind[i]) q[qtail++] = i;
}
while (qhead != qtail) {
int now = q[qhead++];
for (int i = he[now]; i; i = ne[i]) {
Edge &e = ed[i];
d[e.to] = max(d[e.to], d[now] + 1);
if (!--ind[e.to]) q[qtail++] = e.to;
}
}
}

●
首先在建图时记录每个点的入度
●
建立一个队列，把接下来需要访问的点加入队列
●
最开始时所有入度为 0 的点都可以访问，加入队列
●
依次从队列中取出每个点 u ，枚举其出边，边的终点设为 v
-
此处进行各种 u->v 的信息更新
●
因为 u 信息已经计算过了，相当于从图中删去 u ，将其 v 入度 -1
●
此时 v 若入度为 0 则说明前置信息处理完成，加入队列

适用于：有向无环图（ DAG ）：不含有环的有向图

拓扑排序

原文：https://www.cnblogs.com/zyfltyyz/p/11713080.html