前情提要（说给自己的）：别tm再害怕写这玩意了，又不难，码量小，你自己已经写了多少回了自己没数吗，难调吗？不吧。
前情提要（内容的）： dfn 和 low 数组将对Tarjan产生重大影响，所以此处重申这俩的含义—— dfn 是每个点第一次被遍历的顺序， low 是每个点跳一次返祖边能到的最小 dfn

强连通分量

什么是强连通分量

就是有向图上，从任意点开始都能重复相互到达若干次的一堆点，就是一个强连通分量。

怎么求？

好办啊
tarjan基本是一个套路。

那么关于强连通分量，
你拎出这么一棵树，
他上面还有很多杂边，
有从一棵子树插到另一棵的横插边
有返回自己祖先之一的返祖边
有向自己孙子的前向边
当然，可能没有树边吗

上面信息很多、很乱，我们该怎么判断，
首先前向边没有用，
这显然；
其次返祖边有用，
至关重要，
因为它毫无疑问是造出强连通分量的边，
用它可以更新从它到它能达到的那个祖先这一条路上的low；
再说说横插边，
emm~有用但不是非常有用，
它有用是因为它确实可以扩大强连通分量，
提前解释一下，
有不理解的人可能会感觉程序里横插边更新不了，
事实不是这样的，
因为既然自己身为那个横插边连向的已遍历部分的low的子树内一点，
这个点的子树必定没遍历完，
它的强连通分量也就还没结算，
那些已遍历过的部分也就没有退栈，
因而横插边可以更新到这个点。

好了，上代码，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(ll x) {
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;
    for (int i = head[x]; i; i = e[i].next) {
        if (!dfn[e[i].to])
            dfs(e[i].to), low[x] = min(low[x], low[e[i].to]);
        else if (instk[e[i].to])
            low[x] = min(low[x], dfn[e[i].to]);
    }
    if (dfn[x] == low[x]) {
        id++;
        do {
            newid[stk[top]] = id;
            instk[stk[top--]] = 0;
        } while (instk[x]);
    }
}

边双连通分量