强连通分量作用：有向图——>（缩点）有向无环图（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可以用拓扑排序来做
连通分量编号递减的顺序一定是拓扑序