Tarjan 全家桶

2025-05-22T23:09:00+08:00 | 8分钟阅读 | 更新于 2025-05-22T23:09:00+08:00

@
Tarjan 全家桶

十分重要，十分有意义的地方。就和该篇一样。

（左下角本来有人的，我用 PS 修掉了。）

图上连通性。

Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。 Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。并查集、Splay、Toptree 也是 Tarjan 发明的。 摘自 OI-Wiki

一、强连通分量

0、有向图的 DFS 生成树

(1) DFS 序

$u$ 的 DFS 序即为从某节点（根）开始遍历，首次到达 $u$ 的时间戳。

(2) 四条边

  1. 树边：DFS 树上的边。
  2. 返祖边：指向祖先节点的边。
  3. 前向边：指向子孙节点的边。
  4. 横叉边：指向的访问过的节点既不是自己的祖先节点也不是自己的子孙。

如下图，黑边为树边，绿边为返祖边，粉边为前向边，红边为横叉边。


图 $G$

$G$ 的 DFS 生成树

1. 基本概念

  • 强连通：在有向图 $G$ 中，任意两点联通。
  • 强连通分量（SCC）：有向图 $G$ 中，极大的强连通子图。对于“极大”，意思是这个子图无法再加入任意一点使其仍为强连通的。
  • SCC 的根：遍历这个 SCC 的第一个点

1.5 约定

  • $dfn_u$：遍历到 $u$ 的时间戳。
  • $low_u$：以 $u$ 为根的子树可以回溯到最早已经在栈中的节点的时间戳。

2. 求法

Trick

一个 SCC 的所有节点必定在其根的子树中。

我们于 dfs 过程中维护一个栈，里面是未处理的节点。

对于 $u$，我们枚举每一条 $u$ 出边 $(u,v)$。

  • 若 $v$ 未访问。我们向 $v$ 遍历，并更新 $low_u\gets\min(low_u,low_v)$。
  • 若 $v$ 已访问，且在栈内。$low_u\gets\min(low_u,dfn_v)$。
  • 若 $v$ 已访问，不在栈内。那么 $v$ 所在 SCC 已经处理完毕，不操作。

值得注意的是，有时在写强连通分量时，我们误将 $low_u\gets\min(low_u,dfn_v)$ 写作 $low_u\gets\min(low_u,low_v)$，虽然运行结果正确。然而这实际上不符合我们推导以及思考过程，在求双连通分量中这样是错误的。因此需要注意这个问题。

对于一个 SCC，有且仅有一个点使得 $low_u=dfn_u$。

简证

存在性：假设 SCC 根节点为 $R$，那么必然有 $dfn_R=low_R$。这是因为如若 $low_R < dfn_R$，那么说明存在点 $v$ 使 $v$ 加入当前 SCC 点集后仍然是一个 SCC，与定义“极大的”矛盾。

唯一性：除根节点外的所有子节点，必有 $low_u< dfn_u$。这是由于所有子节点都可以回溯到时间戳早于它的节点。

我们只需找到这样的点，将这个点以及栈内所有晚于这个点入栈的点弹出，所构成的即为一个 SCC。

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

void tarjan (int x) {
    dfn[x] = low[x] = ++ tim;
    inst[x] = true;
    st.push (x);

    for (auto to : e[x]) {
        if (!dfn[to]) tarjan (to), low[x] = min (low[x], low[to]);
        else if (inst[to]) low[x] = min (low[x], dfn[to]);
    }

    if (dfn[x] == low[x]) {
        int tp;
        ans.push_back ({});
        do {
            tp = st.top (); st.pop ();
            ans.back ().push_back (tp);
            id[tp] = ans.size ();
            inst[tp] = false;
        } while (tp != x);
    }
}

这整个过程的时间复杂度非常优秀，为 $\mathcal O(n+m)$。

3. 例题

P3387 【模板】缩点

模板题。 我们可以发现，在经过缩点操作后的新图是一个有向无环图，故可以在新图上进行 DP 操作。

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

对原图缩点后，原图中属于出度为 $0$ 的那个点的所有点即为答案。

P2812 校园网络【[USACO]Network of Schools加强版】

缩点，第一个答案为新图入度为 $0$ 点的个数，第二个答案为入度为 $0$ 点个数与出度为 $0$ 点个数的最大值。

P4306 [JSOI2010] 连通数

缩点后建反图，拓扑 DP 即可。 另解：用 bitset 优化的传递闭包。

P2272 [ZJOI2007] 最大半连通子图

原图上是存在环的，所以我们先缩点，得到一张 DAG。根据半连通的定义，我们从入度为 $0$ 的点开始 DP。设 $c_i$ 表示 SCC $i$ 所含节点数，$f_i$ 表示到 $i$ 的最大半连通子图节点数，$g_i$ 表示方案数。那么对于边 $(u,v)$，$f_v\gets \max(f_v,f_u+c_v)$，$g_v\gets\begin{cases}g_u,& f_v<f_u+c_v\g_u+g_v,&f_v=f_u+c_i\end{cases}$。

二、双联通分量，割点与桥

0. 无向图的 DFS 生成树

这部分十分简单，图上边分为树边与非树边。顾名思义。

1. 基本概念

  • 割点：无向连通图 $G$ 中，若删除 $u$ 使得 $G$ 不再连通，那么 $u$ 就是 $G$ 的一个割点。
  • 桥（割边）：无向连通图 $G$ 中，若删除边 $e$ 使得 $G$ 不再连通，那么 $e$ 就是 $G$ 的一个桥。
  • 边双连通：若无向连通图 $G$ 不存在桥，那么 $G$ 就是边双连通的。
  • 点双连通：若无向连通图 $G$ 不存在割点，那么 $G$ 就是点双连通的。
  • 边双连通分量：若 $G’$ 是无向图 $G$ 的 极大 的边双联通子图，那么 $G’$ 就是 $G$ 的一个边双连通分量。下文简称为“边双”。
  • 点双连通分量：若 $G’$ 是无向图 $G$ 的 极大 的点双联通子图，那么 $G’$ 就是 $G$ 的一个点双连通分量。下文简称为“点双”。

这里的“极大”与强连通分量中含义一致。

1.5 约定

  • $dfn_u$：遍历到 $u$ 的时间戳。
  • $low_u$：以 $u$ 为根的子树通过非树边可到达的最小时间戳。
  • $subtree_u$：以 $u$ 为根的子树。

2. 割点 & 点双联通分量

(1) 求割点

类似的，我们考虑 $dfn$ 与 $low$ 的关系。 对于点 $u$ ，若存在 $v\in subtree_u$ 使得 $low_v\ge dfn_u$，也就是说 $v$ 无法通过非树边到达 $u$ 的祖先，那么 $u$ 即为一个割点。特别的，当 $u$ 为搜索起始点时，若其仅有一个子节点，那么删除 $u$ 并不会增加图的连通子图数，因此并不会成为割点；反之，若其多于一个子节点，那么其必然为割点。

简证 命题：$\exist v\in subtree_u,low_v\ge dfn_u\iff u$ 是割点。

若 $v\in subtree_u$，那么 $v$ 是第一次被遍历，且由 $u$ 而来。且对于其到达不在根到 $u$ 路径上的节点的非树边，到达的时间戳必然是大于其本身的。因此当 $low_v\ge dfn_u$ 时，$v$ 必然无法通过非树边到达 $u$ 的祖先。 如若存在这样的 $v$，但 $u$ 不是割点。由于 $v$ 无法通过非树边到达 $u$ 的祖先，故 $v$ 必须通过 $u$ 到达其余点，因此 $u$ 必然为割点。故充分性成立。 如若 $u$ 为割点，假设不存在这样的 $v$：那么所有 $v$ 必然经过 $u$ 到达小于 $low_u$ 的点。然而根据 dfs 的性质，我们发现连接 $u$ 的非树边的 $dfn$ 值是必然大于 $u$ 的，同样的，向上遍历亦如此。故必要性成立。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void tarjan (int x, int root) {
    dfn[x] = low[x] = ++ tim;
    int son = 0;
    for (auto to : g[x]) {
        if (!dfn[to]) {
            tarjan (to, root);
            low[x] = min (low[x], low[to]);
            if (x != root && low[to] >= dfn[x]) cut[x] = true;
            if (x == root) ++ son;
        }  else low[x] = min (low[x], dfn[to]);
    }
    if (x == root && son >= 2) cut[x] = true;
    ans += cut[x];
}

(2) 求点双连通分量

由于点双中不存在割点，因此我们类比求割点的做法，就可以推出点双的做法。 同样的，我们维护一个栈。对于 $u$，我们如果枚举到了 $v$ 使得 $low_v\ge dfn_u$，那么 $u$ 即为割点。并不断弹出栈内元素直至栈顶为 $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
25
26
27

void tarjan (int x, int root) {
    dfn[x] = low[x] = ++ tim;
    st.push (x);

    int son = 0;
    for (auto to : e[x]) {
        if (!dfn[to]) {
            ++ son;
            tarjan (to, root);
            low[x] = min (low[x], low[to]);
            if (low[to] >= dfn[x] ) {
                int tp;
                ans.push_back ({});
                do {
                    tp = st.top (); st.pop ();
                    ans.back ().push_back (tp);
                } while (tp != to);
                ans.back ().push_back (x);
            }
        } else low[x] = min (low[x], dfn[to]);
    }
    if (root == x && !son) {
        ans.push_back ({});
        ans.back ().push_back (x);
        return ;
    }
}

3. 桥 & 边双连通分量

(1) 桥

我们只需将割点的判定条件改为 $low_v>dfn_u$ 即可。证明与上类似。值得注意的是，若 $(u,v)$ 仅有一条边时为桥，多于一条边时，需要特殊判定。若 $v$ 多次枚举到 $u$，那么不为桥。我们只需加上特判即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void tarjan (int u, int fa) {
	dfn[u] = low[u] = ++ tim;
	bool flag = false;
	for (int i = head[u]; i; i = nxt[i]]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan (v, u);
			low[u] = min (low[v], low[u]);
			if (low[v] > dfn[u]) isbridge[i] = isbridge[i ^ 1] = true;
		} else {
			if (flag || v != fa) low[u] = min (low[u], dfn[v]);
			else flag = true;
		}
	}
}

(2) 边双连通分量

我们先把所有桥求出，后再次进行 dfs。具体的，我们枚举每个未被枚举的点 $u$，从 $u$ 开始搜索，将所有不经过桥所连点加入当前的边双集合。这样就得到了全体的边双集合。

1
2
3
4
5
6
7
8
9

void dfs (int x) {
	E_BCC[id].push_back (x);
	vis[x] = id;
	for (int i = head[x]; i; i = nxt[i]) {
		int v = to[i];
		if (vis[v] || isbridge[i]) continue;
		dfs (v);
	}
}

实际上也有另一种简便的求法，与求强连通分量的过程十分相似（实际上一致）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void tarjan (int u, int id) {
    dfn[u] = low[u] = ++ tim; 
    st[++ tp] = u; inst[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        if (i == (id ^ 1)) continue;
        int v = e[i].v;
        if (!dfn[v]) tarjan (v, i), low[u] = min (low[u], low[v]);
        else if (inst[v])           low[u] = min (low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++ coll;
        do {
            col[ st[tp] ] = coll;  
            inst[ st[tp] ] = false;
        } while (st[tp --] != u);
    }   
}

4. 例题

P8435 【模板】点双连通分量 & P8436 【模板】边双连通分量 & P3388 【模板】割点（割顶）

模板题。

P3225 [HNOI2012] 矿场搭建

我们对每一个点双讨论：

  1. 若当前点双不存在割点，则这个点双不与外界相连，因此只能从其本身逃出。那么至少需要两个出口（防止其中之一被炸了）。
  2. 若当前点双存在一个割点，割点可能会被炸，因此我们还需要再这个点双内放置一个出口。
  3. 若当前点双存在不少于两个割点，那么任意一个点爆炸都可以从其他割点逃出。因此无需放置。

那么做法就十分显然了。设出口数为 $cnt$，方案数为 $ans$，当前点双的点数为 $n$。对于度数为 $0$ 的点双，$cnt\gets cnt+2$，$ans\gets ans\times n\times (n-1)\times\dfrac12$。对于度数为 $1$ 的点双，$cnt\gets cnt+1$，$ans\gets ans\times (n-1)$（根据前面的讨论，割点是不能当作出口的）。对于其他度数的点双，我们无需统计。

P8867 [NOIP2022] 建造军营

首先进行边双缩点，后形成一个树结构，两点之间的连边为桥。考虑树形 DP。

© 2025 Toorean's Blog

🌱 Powered by Hugo with theme Dream.