tarjan 求 scc 及其应用

发表于 分类于 ， ，

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

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

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

如何求有向图的 scc:

一般使用 tarjan 算法

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

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

—- 代码 —- 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 解决