Tarjan算法

可以在 $O(n + m)$ 时间内求出有向图的所有强联通分量。

C++模板

// N 表示点数，M 表示边数
int h[N], e[M], ne[M], cnt; // 存储有向图, h[]需要初始化成-1
int belong[N], stap[N], stop, instack[N], dfn[N], low[N], bent, dindex ;
// bent存储强联通分量的个数，belong[i] 存储第i个点处于哪个强联通分量中

void add (int a, int b)
{
    e[cnt] = b ; ne[cnt] = h[a] ; h[a] = cnt ++ ;
}

void tarjan (int i)
{
    dfn[i] = low[i] = ++ dindex ;
    instack[stap[ ++ stop] = i] = 1 ;
    for (int p = h[i]; p != -1; p = ne[p])
    {
        int j = e[p] ;
        if (!dfn[j])
        {
            tarjan (j) ;
            if (low[j] < low[i]) low[i] = low[j] ;
        }
        else if (instack[j] && dfn[j] < low[i]) low[i] = dfn[j] ;
    }

    if (dfn[i] == low[i])
    {
        ++ bent ;
        int j;
        do
        {
            j = stap[stop -- ] ;
            instack[j] = 0 ;
            belong[j] = bent ;

        } while (j != i) ;
    }
}