Tarjan

Tarjan

B3609 [图论与代数结构 701] 强连通分量

std::vector<int> t[maxn]; //vector 存图
std::vector<int> SCC[maxn];
std::stack<int> stk;

int n, m, tot, cnt;
int vis[maxn], dfn[maxn], low[maxn], belong[maxn];

void Tarjan(const int x)
{
    dfn[x] = low[x] = ++tot;
    vis[x] = 1;
    stk.push(x);
    for (int i = 0; i < t[x].size(); ++i)
    {
        int y = t[x][i];
        if (!dfn[y])
        {
            Tarjan(y);
            low[x] = std::min(low[x], low[y]);
        }
        else if (vis[y])
            low[x] = std::min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int Last;
        cnt++;
        do
        {
            Last = stk.top();
            vis[Last] = 0;
            belong[Last] = cnt;
            stk.pop();
            /* 输出强连通分量
            SCC[cnt].push_back(Last);
             */
        } while (stk.size() && Last != x);
    }
    return;
}

signed main()
{
    Init();
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            Tarjan(i);

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < t[i].size(); ++j)
            if (belong[i] != belong[t[i][j]])
                SCC[belong[i]].push_back(belong[t[i][j]]);

    /*  输出强连通分量
    for (int i = 1; i <= n; ++i)
    {
        ll pos = belong[i];
        if (f[pos])
            continue;
        f[pos] = 1;
        sort(SCC[pos].begin(), SCC[pos].end());
        for (int j = 0; j < SCC[pos].size(); ++j)
            printf("%lld ", SCC[pos][j]);

        puts("");
    }
     */
    ......
    
}