题目
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围
1≤n,m≤10e5
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
笔记
问题分析
把每个变量看成一个点, 点与点关系看做有向边（小于）, 于是得到一个有向图。 在一个有向图中把所有节点排序, 使得每一条（u,v）对应的 u 都排在 v 的前面。 这个问题在图论中被称为 拓扑排序（topological sort）
很显然, 如果该图有环, 即一个点u 既在点 v 的前面, 又在点 v 的后面, 此排序在逻辑上是不通的。
不包含有向环的有向图成为有向无环图DAG（Directed Acyclic Graph）
求解策略
当所有 大于 v 的点 处理过后, 便可以处理 v点。 即一个点的 入度 为 0。
那么刚开始时, 遍历整图, 所有初始入度为0的点加入队列中。 假设加入初始入度为0的 点u, 该点有连通v的边, 那么就将v的入度减去1, 以便下一轮处理。
处理操作：
遍历图：
如果该点入度为0：
加入到队列中
遍历u的子节点:
v的入度 -= 1
结果队列末尾 = u
现在处理好头节点后, 如何处理后续节点呢？ 求解过程以层级来分, 第一层我们把初始入度为0的点加入队列中。 接着要处理第二层, 而第二层的点数量由第一层所决定, 第一层剥开后产生的新的入度为0的点 是第二层的点。 接着把第二层的点进行同样的处理得出第三层的点。 直到下一层的点数为0.
这每一层的新加的点如何存储以便于下一轮的处理呢？ 可以用先入先出的队列来存储, 第一层中每个点的子节点若符合要求（入度-1后为0）则加入到队列里, 之后处理队列中的, 直到队列为空则结束。
即
遍历图：
如果该点入度为0：
加入到队列中
若队列不为空：
u = 队列头节点
遍历u的子节点:
v的入度 -= 1
结果数列末尾 = u
核心代码为：
for(int i = 1; i <= n;i ++)
if(!indegree[i])
q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
// 链式图, 邻接矩阵写法参考后文
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(--indegree[j] == 0)
q.push(j);
}
ans[++idx] = j;
}若使用数组模拟队列, 则可以省去 ans 数组
for(int i = 1; i <= n;i ++)
if(!indegree[i])
q[++tt] = i;
while(hh <= tt)
{
int u = q[hh++];
// 链式图, 邻接矩阵与链式图的转换参考我另一篇文章
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(--indegree[j] == 0)
q[++tt] = j;
}
}
for(int i = 0; i < n; i++) // q数组本身便是ans数组
cout << q[i] << " ";如何判断该图是否为有向无环图呢？ 看看ans数组长度是否为n就行
以上求法可以归为 BFS 求法, 还有 DFS 求法, 紫书上便是如此。
如果说BFS是求的入度为0的点, 那么可以说 DFS 求的是出度为0的点。 从图上任意一点开始, 深度搜索子节点, 直到找到出度为0的点, 将该点存入 ans队列的首部（从位置n开始插, 插完将指针左移, 即逆序插入）。 接着将上一个节点继续加入ans, 上上一个节点加入ans, 直到起始节点。
bool dfs(int u){
c[u]=-1;
for(int v=h[u]; v != -1; v = ne[v]) {
int j = e[v];
if(c[j]<0) return false;
else if(!c[j] && !dfs(j)) return false;
}
c[u]=1;
ans[--t]=u;
return true;
}
bool toposort(){
t=n;
for(int i=0;i<n;i++){ if(!c[i])
if(!dfs(i)) return false;
}
return true;
}