无向图的连通性判别【Tarjan 算法】可在线性时间内求出无向图的割点与桥，进一步求解双连通分量等

# 1. 无向图的连通性判别简介

## 1.1 什么是无向图的连通性
在图论中，无向图是由一组顶点和一组边组成的图形结构，其中边没有方向。无向图的连通性是指图中任意两个顶点之间是否存在路径相连。

## 1.2 为什么需要判别无向图的连通性
判别无向图的连通性在很多实际问题中都具有重要意义，比如在网络路由中判断网络中各节点的通信是否畅通，或者在社交网络中寻找朋友关系的强弱连接等。

## 1.3 相关概念介绍
- 连通图：无向图中任意两个顶点之间都存在路径的图称为连通图。
- 连通分量：无向图中的极大连通子图称为连通分量，即在该子图中任意两个顶点之间都存在路径，且与图中其他顶点不连通。

通过对无向图的连通性进行判别，可以帮助我们更好地理解图结构之间的连接关系，为后续的算法设计和应用提供基础。

# 2. Tarjan算法概述

Tarjan算法是一个经典的图论算法，用于解决无向图中的连通性判别问题。本章将对Tarjan算法进行概述，包括其基本原理、时间复杂度分析以及优点与局限性。让我们一起深入了解Tarjan算法的精髓。

# 3. 无向图的割点与桥

在这一节中，我们将深入探讨无向图中的割点和桥的概念，以及如何利用Tarjan算法来找到它们。

#### 3.1 什么是无向图的割点

割点（Articulation Point）是指在去掉这个点（及其连接的边）之后，图会变成不连通的点。换句话说，如果一个点被称为割点，那么这个点的移除将增加图中的连通分量数量。割点是一种在图中起着关键作用的节点，它们可能会影响整个图的连通性。

#### 3.2 什么是无向图的桥

桥（Bridge）是指在去掉这个边之后，图会变成不连通的边。换句话说，如果一条边被称为桥，那么这条边的移除将使得原本连通的图分裂成两个或多个不相连的部分。桥是图中连接两个连通分量的关键边。

#### 3.3 如何利用Tarjan算法求解无向图的割点与桥

Tarjan算法是一种经典的图算法，可以用于寻找图中的割点和桥。在Tarjan算法中，通过对图进行深度优先搜索，并根据搜索过程中的访问顺序和节点信息，可以高效地找到割点和桥。

具体来说，对于每个节点 u，Tarjan算法会维护两个重要的信息：节点 u 的搜索次序编号（dfn[u]）和节点 u 可以追溯到的最早的祖先节点的搜索次序编号（low[u]）。通过判断节点 u 和其相邻节点 v 之间的关系，可以确定是否存在割点和桥。

通过Tarjan算法的精妙设计，我们可以在时间复杂度为 O(V+E) 的情况下找到图中所有的割点和桥，为无向图的连通性判别问题提供了高效且可靠的解决方案。

# 4. 双连通分量

在本章中，我们将深入探讨Tarjan算法在解决无向图的双连通分量相关问题时的应用。首先将介绍什么是双连通分量，然后详细说明如何利用Tarjan算法来求解无向图的双连