tarjan求scc及其应用

---

什么是scc(强连通分量):

在有向图中, 如果若干个点相互可达, 则这几个点构成的集合称为有向图的一个强连通分量

如果把这个图中所有的极大强连通分量变为一个点, 这个图叫scc图。这个图中不存在有向环, 所以scc图是一个DAG

如何求有向图的scc:

一般使用tarjan算法

tarjan借助dfs, 在dfs时记录访问的结点v的时间戳(pre), 并设v及其后代在dfs树上能追溯到的最早的祖先结点为low, 当回溯时如果pre==low, 则说明找到一个scc。

用一个栈辅助存储dfs中子树的结点, 当找到scc时将栈中的结点弹出, 弹出的结点即是scc中的结点。

——代码——

int t(0); //时间戳
int pre[Mn], low[Mn], scc[Mn] //pre,low,结点的scc编号
int scn(0); //scc计数器
stack<int> S; //辅助存储
void tarjan(int x)
{
    pre[x] = ++t;
    low[x] = t;
    S.push(x);
    for(int i(0);i<G[x].size();++i)	//遍历有向边
    {
        int& v(G[x][i]);
        if(!pre[v]) //如果未访问, 即访问到的是子结点
        {
            tarjan(v); //dfs
            low[x] = min(low[x],low[v]);
        }
        else if(!scc[v]) //如果访问到的是祖先节点
            low[x] = min(low[x],pre[v]);
    }
    if(pre[x]==low[x])
    {
        ++scn;
        while(true)
        {
            int u(S.top()); S.pop();
            scc[u] = scn;
            if(u==x)	break;
        }
    }
}

tarjan算法的作用:

首先, scc是由一个或多个环组成的, 可以用tarjan来寻找有向图中的环

最主要的是, 将有向图缩点形成的scc图是一个DAG, 对于有向非DAG的最优解, 可以先用tarjan将图缩成DAG, 然后使用dp解决