相关概念

强连通：在有向图 $D$ 中，$D$ 的任意两个节点连通

强连通分量：一张平凡图上的极大强连通子图

DFS 生成树：以图上某节点通过 DFS 访问的方式，与可达节点形成的树结构，依据树结构图上的边主要分为四类

树边：在 DFS 生成树上连接两个节点的边，在图上为每次搜索找到一个还没有访问过的结点时通过的一条边

返祖边：图上的一条边，他的始点在 DFS 生成树上的祖先是这条边的终点

横叉边：图上的一条边，他的始点在 DFS 生成树上的祖先不是这条边的终点，但终点在之前已经被访问过

前向边：图上的一条边，他的始点在 DFS 生成树上的儿子是这条边的终点

返祖边与树边一定能构成环，横叉边与树边可能构成环

强连通分量的根：某强连通分量在 DFS 生成树中遇到的第一个节点，该强连通分量的其余节点一定也在这个节点为根的子树中

Tarjan算法

对每个节点 $x$ 都维护出它在 DFS 搜索树上的时间戳 $dfn_x$（DFS 过程中被搜索到的次序），以及 $x$ 能访问到的最早时间戳 $low_x$ （追溯值）

vector<int> e[N];
vector<int> stk;//模拟栈
int dfn[N],low[N],tot;
int scc[N],siz[N],cnt;
bool instk[N];

void tarjan(int x){
    dfn=low=++tot;
    stk.push_back(x),instk=1;
    for (auto v:e){
        if (!dfn[v]){
            tarjan(v);
            low=min(low,low[v]);
        }else if (instk[v])
            low=min(low,dfn[v]);
    }
    
    if (low==dfn){
        int t;
        cnt++;
        do{
            t=stk.back();
            stk.pop_back();
            instk[t]=0;
            scc[t]=cnt;
            siz[cnt]++;
        }while (t!=x);
    }
}

每进入一个节点时，初始化节点的 $dfn_x,low_x$ 为当前的次序号 $tot$，并将这个节点放进栈中，标记节点已入栈

枚举当前节点的邻边，根据不同类型进行操作

for (auto v:e){
    if (!dfn[v]){//如果邻点还没有被访问到，则该边为树边
        tarjan(v);//dfs访问v
        low=min(low,low[v]);//返回更新当前x的追溯值
    }else if (instk[v])//如果v被访问，且在栈内，则该边为横叉边或返祖边
        low=min(low,dfn[v]);//返回更新当前x的追溯值
}

如果一个节点在遍历完它的所有儿子后，$dfn_x$ 没有变小那么说明他就是一个强连通分量的根（在他可连通的节点中不存在能够到达之前访问过的节点），依次取出栈内元素，直到栈顶元素为 $x$

if (low==dfn){
    int t;
    cnt++;//强连通分量数+1
    do{
        t=stk[top--];//取出栈顶元素
        instk[t]=0;//标记出栈
        scc[t]=cnt;//更新栈顶元素所在的强连通分量
        siz[cnt]++;//记录该强连通分量拥有的节点数
    }while (t!=x);
}

核心思想是通过 $low_x$ 判断是否能回到 $DFS$ 路径的起点，从而切割出 $scc$

Kosaraju算法

第一遍 DFS 处理出每个节点的时间戳，回溯时将时间戳较大的节点放进栈内（强连通分量的根一定是最后完成的）

根据这样一个结论：将一个强连通分量中所有边反向后，形成的仍然为一个强连通分量

从栈顶依次取元素，如果该点未处于一个强连通分量中，那对该节点进行第二次 DFS，在逆图中枚举他能够到达的所有点，这些点集构成一个极大强连通分量

每次取出的元素，都作为他所在强连通分量的根

int n,m;
vector<int> e[N],re[N];
vector<int> stk;
bool vis[N];
int scc[N],siz[N],cnt;

void dfs1(int x){
    if (vis) return;
    vis=1;
    for (auto v:e)
        dfs1(v);
    stk.push_back(x);
}

void dfs2(int x){
    if (scc) return;
    scc=cnt;
    siz[cnt]++;
    for (auto v:re)
        dfs2(v);
}

void kosaraju(){
    for (int i=1;i<=n;i++)
        if (!vis[i])
            dfs1(i);
    for (int i=stk.size()-1;i>=0;i--){
        if (!scc[stk[i]]){
            ++cnt;
            dfs2(stk[i]);
        }
    }
}

核心思想在于划分一个强连通分量前，封锁他与外界连通的道路