图论---有向图的强连通分量（Tarjan求SCC）

强连通分量作用：有向图——>（缩点）有向无环图（DAG）

缩点：将所有连通的分量缩成一个点。

有向无环图作用/好处：求最短路/最长路 可以递推，按照拓扑图从前往后递推.

x 是否在某个强连通分量中？

情况1：存在后向边指向祖先节点。

情况2：先走到横叉边，横叉边再走到祖先。

时间戳：搜索时按照DFS顺序给每个点一个编号，

对每个点定义两个时间戳：

1、dfn[u] 表示遍历到 u 的时间戳

2、low[u] 从 u 开始走，所能遍历到的最小的时间戳是什么

u 是其所在强连通分量的最高点 等价于 dfn[u] == low[u]

 以下是Tarjan模板

//O(n+m)时间复杂度
//求强连通分量的过程
void tarjan(int u){//刚遍历到的时候dfn[u]=low[u]=++timestamp;//时间戳stk[++top]=u,in_stk[u]=true;//栈中里面存的所有点都是//当前还没有遍历完的强连通分量的所有点//在强连通分量中，并且这个强连通分量还没有遍历完//遍历所有 u 能到的点for(int i=h[u];~i;i=ne[i]){int j=e[i];//u 还没被遍历过if(!dfn[j]){//遍历一下这个点tarjan(j);low[u]=min(low[u],low[j]);}else if(in_stk[j]){low[u]=min(low[u],dfn[j]);}}//else 里面的 j 要么是祖先要么是横叉点if(dfn[u]==low[u]){int y;++scc_cnt;do{y=stk[top--];in_stk[y]=false;id[y]=scc_cnt;}while(y!=u);}
}缩点
用邻接表存
遍历所有点，遍历 i 的所有邻点
if(i 和 j 不在同一个SCC中){加一条新边 id[i] -> id[j] 存的是i所在的连通分量的编号
}
建成的图是 有向无环图
DAG可以用拓扑排序来做
连通分量编号递减的顺序一定是拓扑序