拓扑排序

把一个图的所有节点排序，使得每一条有向边$(u, v)$对应的$u$都排在$v$的前面。在图论中，这个问题称为拓扑排序(topological sort)。

不难发现：如果图中存在有向环，则不存在拓扑排序，反之则存在。所以可以用拓扑排序来检验是否存在有向环。

BFS

首先要找出所有的起点，也就是所有入度为0的点。入度为0的点在DAG中是一定存在的。（证明在这篇博客中可以找到）

若是队列不空，取出队列头$x$，遍历所有起点是$x$的边。

每次遍历中，更新数据，并删除这条边，代码实现就是这条边的终点$y$的入度减一。

如果$y$的入度被减为0，则说明$y$的所有前驱都被计算过了，$y$成了新的起点，将$y$插入队列。

如此循环直至队列空。

最后统计数据。

如果要判定有向环，要加一个vis[]， 确保每个点只访问一次。

//这里我用邻接表储存边
//把一条边的信息封装到edge结构体内
for(int i=1;i<=n;i++){
	if(inDeg[i]==0) Q.push(i);
}

while(!Q.empty()){
	int f=Q.front();
	
	for(int i=0;i<G[f].size();i++){
		edge e=G[f][i];
		inDeg[e.to]--;
		//更新数据
		if(inDeg[e.to]==0){
			Q.push(e.to);
		}
	}
	
	Q.pop();
}

DFS

《算法竞赛入门经典》里还给出了一种DFS的拓扑排序，这里只是输出一张图的拓扑排序。

int c[maxn];
int topo[maxn], t;
bool dfs(int u){
    c[u]=-1; //访问标志
    for(int v=0;v<n;v++) if(G[u][v]){
        if(c[v]<0) return false; //存在有向环，失败退出
        else if(!c[v] && !dfs[v]) return false;
    }
    c[u]=1;topo[--t]=u;
    return true;
}

bool toposort(){
    t=n;
    memset(c, 0, sizeof(c));
    for(int u=0;u<n;u++) if(!c[u])
        if(!dfs[u]) return false;
    return true;
}

这里用到了一个 c 数组，c[u]=0 表示从来没有访问过（从来没有调用过dfs(u)）；c[u]=1 表示已经访问过，并且还递归访问过它所有的子孙（即dfs(u)曾被调用过，并已经返回）；c[u]=-1 表示正在访问（即递归调用dfs(u)正在栈帧中，尚未返回）。

参考

https://www.luogu.com.cn/blog/106510/topo-sort

《算法竞赛入门经典》