tarjan算法与拓扑排序
2021-04-21 00:28
标签：const 结束 统计 order 简单 步骤 强联通 排序 com tarjan算法要求使有向图。 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 P3387 【模板】缩点 tarjan算法与拓扑排序 标签：const 结束 统计 order 简单 步骤 强联通 排序 com 原文地址：https://www.cnblogs.com/wangqianyv/p/13283049.html算法介绍
tarjan
Tarjan就是一个辅助作用，把有环图缩为无环图，也就是将强联通分量缩成一个点。
几个数组 dfn时间戳，low仍在栈中的最小时间戳，dag缩点后的数组，ins是否在栈中。void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
ins[x]=1;
st.push(x);
for(int i=0;i拓扑排序
拓扑排序步骤
统计入度，入度为0入栈，递推并更新入度，入度为0入栈，栈空结束queue例题
代码
const int maxn=100015;
int numb,cnt;
int dist[maxn];
int dag[maxn],num[maxn];
int a[maxn];
int ind[maxn];
stack