Tarjan强连通分量与缩点

amcones 收录于 Algorithm Graph Theory

2022-11-04 约 559 字预计阅读 2 分钟 - 次阅读

之前就没有很搞懂dfs搜索树的顺序，这次好好搞一下。

概念

强连通：两个点互相可达称为强连通连通分量：一个集合中的顶点互相可达，称为连通分量强连通分量：每个集合中最大的连通分量。

dfs搜索树上边分为四大类（jls的集训队论文也提到了）

树枝边（父节点与子节点之间的边、特殊的前向边）
前向边（每个点到后代的点）
后向边（每个点到祖先的点）
横叉边（往其它分支搜索的时候产生）

判是否在强连通分量中：

存在后向边指向祖先节点
先走到横叉边，再走到祖先。

Tarjan

引入时间戳的概念判断在dfs中被搜到的顺序（是否和dfs序是一个东西？）

对每个点定义两个时间戳：

dfn[u]遍历到u的时间戳
low[u]从u开始走，所能遍历到的最小时间戳

u是其所在的强连通分量的最高点，等价于dfn[u]==low[u]

如果还能往上走，就说明强连通分量还没搜完。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u), in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        int y;
        scc_cnt++;
        do {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sum[scc_cnt] += a[y - 1];
        } while (y != u);
    }
}

缩点

1
2
3
4


遍历所有点
    遍历 i 的所有邻点 j
        如果 i 与 j 不在同一SCC中
            加一条新边 id(i)->id(j)

连通分量编号递减的顺序一定是拓扑序，不需要缩点后再写拓扑排序

感性认识一下，编号越大的越靠上，那么从大到小是拓扑序也挺合理的（