第 4 章 · 03 连通分量与二分图(对应 docs/graph/)

第 4 章 · 03 连通分量与二分图(对应 docs/graph/)

本节定位:对应 OI Wiki docs/graph/ 连通性部分。难度:进阶。前置依赖:本章 01-02 节(图论基础 + 网络流)+ 第 3 章(并查集)。

⚠️ 注意:这一节里 Tarjan 算法是图论核心。它用一个 DFS 就能求强连通分量、割点、桥、双连通分量——四种问题一套代码框架。学不会 Tarjan,图论就算没入门。务必慢节奏精读 docs/graph/scc.md / docs/graph/cut.md。

知识地图

docs/graph/ 页面地图(连通性部分)

docs/graph/ 里连通性相关页面:

强连通与缩点

• docs/graph/scc.md:强连通分量(SCC),Tarjan 与 Kosaraju 两种算法。
• docs/graph/connectivity.md:连通性总览。

双连通

• docs/graph/cut.md:割点与桥(Tarjan)。
• docs/graph/bcc.md:双连通分量(点双 BCC / 边双 EBCC)。
• docs/graph/block-forest.md:点双/边双缩点后的圆方树 / 缩点树。

2-SAT

• docs/graph/2-sat.md:2-SAT(布尔可满足性,建模为 SCC)。

欧拉

• docs/graph/euler.md:欧拉回路与欧拉路径(一笔画)。

二分图

• docs/graph/bi-graph.md:二分图总览。
• docs/graph/color.md:二分图判定(染色法 BFS/DFS)。
• docs/graph/graph-matching/:图匹配子目录(匈牙利/KM,见第 02 节)。

树相关(部分散在 graph 目录)

• docs/graph/tree-basic.md:树基础。
• docs/graph/lca.md:最近公共祖先 LCA(倍增 / Tarjan)。
• docs/graph/hld.md:树链剖分(重链剖分)。
• docs/graph/tree-divide.md:点分治。
• docs/graph/tree-centroid.md:树的重心。
• docs/graph/tree-diameter.md / docs/graph/tree-center.md:树的直径 / 中心。
• docs/graph/virtual-tree.md:虚树。
• docs/graph/dsu-on-tree.md:dsu on tree(树上启发式合并)。

强连通分量 SCC

docs/graph/scc.md。强连通:有向图中两点互相可达。强连通分量是极大强连通子图。

Tarjan 算法(一次 DFS):维护两个数组:

• dfn[u]:u 的 DFS 时间戳。
• low[u]:u 或 u 的子树能回溯到的最早(最小 dfn)的祖先。

核心:DFS 遇到 u 给 dfn[u] = low[u] = ++timer,入栈。扫每条出边 (u,v):

• 若 v 未访问:递归 v,回溯后 low[u] = min(low[u], low[v])。
• 若 v 在栈中:low[u] = min(low[u], dfn[v])。

当 dfn[u] == low[u] 时,u 是一个 SCC 的根,弹栈直到 u,这些点构成一个 SCC。

void tarjan(int u){
  dfn[u]=low[u]=++timer; stk[++top]=u; in[u]=1;
  for(int i=head[u]; ~i; i=nxt[i]){
    int v=e[i].to;
    if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }
    else if(in[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]){
    int v; ++scc_cnt;
    do{ v=stk[top--]; in[v]=0; bel[v]=scc_cnt; }while(v!=u);
  }
}
​

Kosaraju 算法(两次 DFS):第一次在原图 DFS 记录后序;第二次在反图按后序逆序 DFS,每次能到的点构成一个 SCC。比 Tarjan 直观但慢一倍,竞赛少用。

缩点

把每个 SCC 缩成一个点,得到 DAG(有向无环图)。缩点后:

• 可以做拓扑序 DP:在 DAG 上跑最长路 / 路径计数 / 树形 DP。
• 经典题:最大半连通子图、受欢迎的牛(洛谷 P2341)、缩点后最长链。

// 缩点:扫所有边 (u,v),若 bel[u]!=bel[v],新图加边 bel[u]->bel[v]
for(int u=1;u<=n;u++)
  for(每条边(u,v))
    if(bel[u]!=bel[v]) newG.add(bel[u], bel[v]);
​

双连通分量

docs/graph/cut.md + docs/graph/bcc.md。无向图概念:

• 割点:删掉这个点后图不连通。
• 桥(割边):删掉这条边后图不连通。
• 点双连通:任意两点间至少两条点不重复路径(没有割点)。
• 边双连通:任意两点间至少两条边不重复路径(没有桥)。

Tarjan 同样用 dfn / low 判定:

• v 是 u 的儿子且 low[v] >= dfn[u]:u 是割点(根节点除外,根是割点当且仅当有两个以上 DFS 子树)。
• v 是 u 的儿子且 low[v] > dfn[u]:边 (u,v) 是桥。

点双 / 边双的求法也是基于 Tarjan,细节见 docs/graph/bcc.md。圆方树(docs/graph/block-forest.md)是点双缩点后的优美结构,省选题常用。

2-SAT

docs/graph/2-sat.md。布尔变量每变量取 true/false 之一,约束是"若 A 则 B"这种二元蕴含。建模:

• 每个变量 x 拆成两个点:x 和 \neg x。
• 约束"A \lor B"拆成两条蕴含边:\neg A \to B 和 \neg B \to A。
• 跑 SCC。若 x 和 \neg x 在同一 SCC,无解。否则,x 取"SCC 编号大"的那个值(Tarjan 先求出的 SCC 编号是逆拓扑序)。

2-SAT 是 SCC 的经典应用,NOIp 级别常考。

欧拉回路 / 欧拉路径

docs/graph/euler.md。

• 欧拉回路:经过每条边恰好一次的回路。存在条件:无向图所有点度数为偶数且连通;有向图所有点入度=出度且连通。
• 欧拉路径:经过每条边恰好一次的路径。无向图恰有 0 或 2 个奇度点。

求解:Hierholzer 算法,DFS 每条边走过就删,回溯时把点加入路径,最后逆序输出。

二分图判定与匹配

docs/graph/bi-graph.md + docs/graph/color.md。

判定:BFS 或 DFS 染色,相邻点不同色。能成功染色就是二分图(等价于图无奇环)。

匹配:见第 02 节,匈牙利 O(VE) / KM O(V^3) / 最大流建模。

学习建议

Tarjan 是图论核心必精

💡 学习提示:Tarjan 一套框架求四种东西(SCC / 割点 / 桥 / BCC),关键区别在 dfn 和 low 的比较条件(>= / >)和判定时机。建议:对比着学,把这四个版本的代码放一起,看清它们的差异和共性。Wiki docs/graph/scc.md 和 docs/graph/cut.md 都有完整代码,精读后默写。

学习顺序

1. SCC Tarjan(★ 必精)— 强连通分量基础
2. 缩点 + 拓扑序 DP(SCC 的应用)
3. 割点 / 桥(★ 必精)— 无向图 Tarjan
4. 点双 / 边双(进阶)
5. 2-SAT(SCC 的经典应用)
6. 欧拉回路(Hierholzer)
7. 二分图判定 + 匹配(第 02 节延伸)
8. 树相关(LCA / 树链剖分 / 点分治,逐步学)

每个配套模板题:

• 洛谷 P2341 受欢迎的牛(SCC + 缩点)
• 洛谷 P3387 【模板】缩点(SCC + 拓扑 DP)
• 洛谷 P3388 【模板】割点
• 洛谷 P1656 炸铁路(桥)
• 洛谷 P4782 【模板】2-SAT
• 洛谷 P7771 【模板】欧拉路径

Tarjan 的难点:low 的更新规则

low[u] 的更新有两种写法,极易混淆:

• 写法 A(Tarjan 原版):low[u] = min(low[u], dfn[v])(看 v 的时间戳)
• 写法 B(另一种):low[u] = min(low[u], low[v])(看 v 的 low)

对 SCC,两种写法都能 AC(但有细微差别,见 Wiki 讨论)。对割点割边,推荐 A。初学固定一种,不要混用。Wiki docs/graph/scc.md 末尾有详细讨论,值得读。

常见误区

⚠️ 注意:

1. Tarjan 根节点判定:割点判定时根节点(u 是 DFS 树根)特殊——它是割点当且仅当有多个DFS 子树,不是看 low[v] >= dfn[u]。
2. low 更新规则混用:写法 A 和写法 B 混用会出错。固定一种。
3. SCC 缩点后忘判重边:缩点新图可能有重边,如果是求最长链要忽略,如果是网络流建模可能要保留。
4. 2-SAT 蕴含边方向建反:"A 或 B" 等价于"非 A 则 B"和"非 B 则 A",方向反了就错。
5. 欧拉回路忘删边:DFS 走过的边要删(或标记),否则会重复走、栈溢出。用链式前向星时,可以用 head[u] = nxt[i] 直接删当前边。
6. 二分图染色忘处理不连通图:要对每个未访问点都跑一遍 BFS/DFS 染色。

本节要点

1. docs/graph/ 连通性:SCC(强连通)/ 割点 / 桥 / 双连通(点双/边双)/ 2-SAT / 欧拉 / 二分图。
2. ★ Tarjan 是图论核心:一次 DFS,用 dfn/low 求四种东西,差别在比较条件(>= / >)和判定时机。
3. SCC 缩点得到 DAG,可做拓扑序 DP(最长链、路径计数);2-SAT 建模为 SCC,根据 SCC 编号取值。
4. 割点:根特判,非根看 low[v] >= dfn[u];桥看 low[v] > dfn[u]。
5. 欧拉回路 Hierholzer 算法(走边即删,回溯入路径,逆序输出);二分图判定 BFS 染色,匹配见第 02 节。