1 基本概念
1.1 图与连通性的回顾
在图论中，图由顶点和边构成，用来描述对象之间的连接关系。对于无向图而言，如果任意两个顶点之间都存在一条路径，就称该图是连通的；否则，它可被分成若干彼此独立的连通部分，即连通分量。
连通性描述的是图是否“通路完整”。当讨论某个子结构在删除局部元素后是否仍能保持整体联通时，就会进一步引出更强的连通概念，这也是双连通分量出现的背景。
1.2 双连通性的定义
双连通性通常用来描述一种更稳固的连接状态。相较于普通连通性，它要求图在失去某些局部元素后，仍然不容易被切断。根据研究对象不同，双连通性可分为点双连通与边双连通两类。
1.2.1 点双连通
点双连通强调“删去一个顶点后仍保持连通”。若一个无向图中任意删除一个顶点（以及与之相连的边）后，剩余图仍连通，则该图具有点双连通性质。这样的图不存在割点，因此结构较为稳固。
1.2.2 边双连通
边双连通则关注边的删除影响。若一个无向图在删除任意一条边后仍保持连通，则称其具有边双连通性质。此时图中不会存在桥，因为桥一旦被移除，图就会断开。
1.3 双连通分量的含义
双连通分量是满足双连通性质的极大子图。这里的“极大”表示：不能再加入更多顶点或边而仍保持同样性质。点双连通分量和边双连通分量分别对应点双连通与边双连通的极大部分，用于刻画图中结构最紧密的区域。
在实际分析中，双连通分量常被视为“不会轻易碎裂”的核心单元，适合用来研究网络骨架、局部稳健子结构以及关键连接点。
1.4 与连通分量的区别
连通分量只要求内部任意两点可达，不关心删除某些点或边后的稳定性；双连通分量则要求更强，强调结构对单点或单边失效的抗性。因此，一个连通分量内部可能包含多个双连通分量，也可能被割点或桥进一步切分。
换言之，连通分量回答“是否连在一起”，双连通分量回答“连得是否牢靠”。
2 相关图论术语
2.1 割点
割点是无向图中具有“切断作用”的顶点。删除该顶点及其关联边后，图的连通块数增多，则该顶点就是割点。它在图结构中往往对应薄弱环节。
2.1.1 割点的判定
在深度优先搜索中，若某个顶点的子树无法通过返祖边回到其祖先，那么该顶点可能成为割点。特别地，若非根节点满足某个子树的最早可达祖先位置不早于自身，就说明去掉它会使部分区域失去与上层的联系。
2.1.2 割点与双连通分量的关系
割点通常位于多个点双连通分量的交界处。一个割点可以同时属于若干个点双连通分量，起到“连接多个块”的作用。正因如此，点双连通分量并不是简单彼此独立，而是通过割点形成链式或树状的关联结构。
2.2 桥
桥是删除后会使图连通性下降的边。它是边层面的薄弱环节，常被看作网络中的单点故障边。
2.2.1 桥的定义
在无向连通图中，如果删除某条边后，图变得不连通，则该边称为桥。桥所在位置往往连接着两个原本较为独立的区域，因此一旦去除，结构便会断裂。
2.2.2 桥与边双连通分量的关系
边双连通分量的划分常以桥为分界线。删除所有桥后，剩余图的每个连通块就是一个边双连通分量。也就是说，桥把边双连通区域切成若干部分，而这些部分内部不含桥。
2.3 块与块树
“块”在点双连通分析中经常出现，常用来表示一种内部无割点或对应某类极大稳固区域的结构。块树则是把这些块和割点组织起来形成的树状表示。
2.3.1 点双连通分量中的块
在很多教材和应用语境中，块可视为点双连通分量。它表示一组顶点及其边所构成的较强连通单元，内部不易因单个点的删除而解体。块之间可能共享割点，因此整体结构并不彼此完全分离。
2.3.2 块树的结构
块树是一种二分树结构，通常由“块节点”和“割点节点”构成。若某割点属于某个块，就在对应两类节点之间连边。这样可把原图中复杂的点双连通关系压缩成树形，便于分析与遍历。
3 性质与定理
3.1 点双连通分量的基本性质
3.1.1 最大性
点双连通分量是点双连通子图中的极大者，不能再通过加入更多顶点而保持点双连通。若继续扩展会引入割点或破坏删除单点后的连通性，则扩展后的集合不再符合定义。
3.1.2 覆盖性
原图中的每条边、每个顶点都至少会出现在某个点双连通分量或其相关结构中。对连通图而言，点双连通分量及割点共同覆盖了图的全部重要连接信息，因此不会遗漏核心部分。
3.1.3 唯一分解性
在给定无向图中，点双连通分量的划分方式具有确定性，不依赖于遍历顺序。虽然不同算法的输出顺序可能不同，但分量本身是唯一的，这使其适合作为图结构分析的标准单元。
3.2 边双连通分量的基本性质
3.2.1 删除桥后的分解
边双连通分量可以通过删去所有桥后得到。桥将原图分割成若干边双连通部分，而这些部分内部任意两点之间都存在不经过桥的连接路径，因此在边意义下较为稳固。
3.2.2 极大性与连通性
每个边双连通分量都是连通的，并且在不破坏边双连通性质的前提下已经不能继续扩大。若再并入其他部分，就可能跨越桥，从而使删除某条边后出现断裂。
3.3 双连通分量之间的关系
3.3.1 与割点共享顶点的情况
点双连通分量之间常通过割点相连。一个割点可能同时属于多个分量，形成“多块交汇”的结构。这种共享方式使得原图可以被拆解为若干局部稳定块，再由割点串联起来。
3.3.2 与桥连接的情况
在边双连通分析中，桥往往连接两个不同的边双连通分量。桥本身不属于任何更大范围的边双连通核心，而是分量之间的脆弱连接点。删除桥后，各分量彼此分离，图的层次关系因此变得清晰。
4 算法
4.1 Tarjan算法
Tarjan算法是图论中处理连通性与分量划分的经典深度优先搜索框架，广泛用于寻找割点、桥以及双连通分量。它的核心思想是借助时间戳和回溯信息，判断顶点或边在图中的“可回到更早祖先”的能力。
4.1.1 DFS时间戳
在深度优先搜索中，每个顶点都会被赋予一个访问顺序编号，称为时间戳。该编号反映了顶点被首次访问的先后次序，是后续比较祖先关系的重要依据。
4.1.2 low数组的作用
low数组记录的是一个顶点及其子树，通过树边和返祖边能够到达的最小时间戳。它刻画了当前搜索子树向上连接的最早位置，因而成为识别割点、桥和分量边界的关键量。
4.1.3 识别割点与双连通分量
当某个顶点的子树无法通过返祖边回到其祖先时，就说明该点在结构中起到分隔作用，可据此判断割点。类似地，通过时间戳与low值的比较，也能确定哪些边或顶点属于同一个双连通区域。
4.2 求点双连通分量的算法
4.2.1 栈维护边或点
求点双连通分量时，常使用栈保存搜索过程中经过的边，或者在某些实现中保存相关顶点。栈记录了当前尚未确定归属的结构片段，便于在找到分量边界时一次性弹出。
4.2.2 分量提取过程
当DFS回溯到某个边界条件时，说明某一部分已构成一个完整的点双连通分量。此时从栈中弹出对应边，直到覆盖该分量的全部元素，即可得到一个独立的块。重复这一过程，便能完成整个图的划分。
4.3 求边双连通分量的算法
4.3.1 缩桥成树的思路
先找出所有桥，再将非桥边连接的顶点视为同一组。这样得到的每个组就是一个边双连通分量，而桥则成为分量之间的连线。进一步压缩后，常形成一棵树或森林，便于后续分析。
4.3.2 并查集与DFS方法
边双连通分量也可通过并查集维护连通关系：先用DFS标记桥，再把非桥边连接的顶点合并到同一集合中。相比单纯遍历，这种方式实现简洁，适合在桥判定之后快速完成分量归并。
4.4 复杂度分析
4.4.1 时间复杂度
Tarjan类算法通常只需一次或少数几次深度优先搜索即可完成，整体时间复杂度一般为线性级别，即与顶点数和边数之和成正比。这使其适合处理大规模图数据。
4.4.2 空间复杂度
算法空间主要来自图的存储、递归栈、辅助数组以及分量栈等，通常也保持在线性规模。只要输入图的表示方式合理，额外开销一般可控。
5 构造与表示
5.1 图的存储方式
5.1.1 邻接表
邻接表适合稀疏图，是求双连通分量时最常见的数据结构。它能高效遍历每个顶点的相邻边，并且便于在DFS中记录边编号和父边信息。
5.1.2 邻接矩阵
邻接矩阵更适合顶点数较少或需要快速判断任意两点是否相连的场景。虽然直观，但在大图中空间开销较大，因此在双连通分量算法里较少作为首选。
5.2 分量的标记与编号
5.2.1 顶点编号
在分量构建过程中，通常会为每个顶点分配所属分量编号。这样可以快速判断两个顶点是否处于同一双连通区域，也便于后续构建缩点图。
5.2.2 边编号
对边进行编号有助于区分多重边、记录父边、避免重复访问，并在基于边的栈操作中准确回溯。尤其在桥和分量提取时，边编号能显著提升实现清晰度。
5.3 分量图的构建
5.3.1 缩点
缩点是将原图中的一个分量压缩为一个新节点。经过缩点后，图会从复杂结构转化为更简洁的抽象图，常用于研究分量之间的连接关系。
5.3.2 构造树状结构
若对双连通分量进一步压缩，往往可以得到树状或近似树状结构。点双连通场景下常形成块树，边双连通场景下则常得到桥树或分量树，便于进行层次化分析。
6 应用
6.1 网络可靠性分析
双连通分量常用于评估网络的容错能力。若某个区域属于点双连通或边双连通结构，则说明该区域对单点或单边失效具有更强抵抗力，适合用于关键基础设施、通信网络与拓扑稳定性分析。
6.2 关键节点与关键边识别
割点和桥是图中的关键薄弱元素，识别它们能够快速定位网络中最容易造成断裂的位置。双连通分量分析可将“稳定部分”和“脆弱连接”区分开，从而支持故障排查与结构诊断。
6.3 无向图结构优化
在图优化问题中，先划分双连通分量再进行处理，往往能够降低问题规模。通过缩点后的结构做动态规划、最短路分析或路径统计，通常比直接在原图上操作更高效。
6.4 竞赛编程中的典型题型
双连通分量是算法竞赛中的高频内容，常与DFS、Tarjan、缩点图等知识点联动出现。题目往往要求识别关键点、构造分量、统计结构数量，或者在缩点后完成进一步计算。
6.4.1 求割点与桥
这类题目通常要求输出所有割点和桥，或判断某条边是否为桥。核心在于正确维护时间戳与low值，并处理根节点与非根节点的不同判定规则。
6.4.2 求双连通分量
题目可能要求找出所有点双连通分量或边双连通分量，并统计每个分量的大小、边数或成员。实现时往往需要栈、DFS以及分量提取流程的配合。
6.4.3 构建缩点图
有些问题会先将原图压缩成分量图，再在新图上求解。缩点图通常更简洁，适合进行路径分析、树上DP或连通性统计，是竞赛中常见的处理技巧。
7 示例与直观理解
7.1 简单图示例
设有一个三角形图，三个顶点两两相连。对于点双连通而言，删除任意一个顶点后，剩下的两个顶点仍然连通，因此整个三角形就是一个点双连通分量。
7.2 含割点的图示例
若两个三角形只通过一个公共顶点连接，那么这个公共顶点就是割点。两个三角形分别构成不同的点双连通分量，而共享顶点把它们串联起来，体现出“局部稳固、整体分层”的特征。
7.3 含桥的图示例
若一个大图中有一条边仅连接两个子区域，且删去该边后图会分成两部分，那么这条边就是桥。桥两侧的区域各自可能是边双连通分量，而桥则是它们之间唯一的连接通道。
7.4 分量划分过程演示
在DFS过程中，算法会沿边深入搜索，并利用low值判断回退能力。当某段搜索路径无法再回到更早祖先时，就会在栈中弹出一组边或顶点，形成一个完整分量。这样逐步回溯，最终即可得到全图的双连通分量划分。
8 相关扩展
8.1 强连通分量的对比
强连通分量是有向图中的概念，要求任意两点之间都能沿有向边互相到达。它与无向图中的双连通分量类似，都是对图进行结构分块，但判断标准和算法场景并不相同。
8.2 三连通性与更高阶连通性
除了点双连通和边双连通，还可以进一步研究三连通性及更高阶连通性。这些概念要求图在删除更多顶点或边后仍保持连通，反映了更强的结构稳定性，但分析难度也更高。
8.3 有向图中的相关概念
在有向图中，与连通性相关的概念主要围绕强连通、可达性和环结构展开。虽然不直接对应无向图的双连通分量，但在算法思想上同样会用到DFS、栈和缩点等工具，因此二者在方法论上有一定相通之处。