Tarjan 算法求点双连通分量
关于边双连通分量的求法，请参阅"Tarjan 算法求边双连通分量"。 本文部分内容参考自 lyd 的《算法竞赛进阶指南》。
基础概念回顾 给定一个无向连通图 \(G=(V,E)\)：
- 割点 (Cut Vertex)：若图中存在一个顶点 \\(x\\)，删除该顶点及其所有关联边后，图 \\(G\\) 分裂成两个或多个不连通的子图，则称 \\(x\\) 为图 \\(G\\) 的割点。
- 时间戳 (Timestamp)：在深度优先搜索 (DFS) 过程中，为每个顶点首次被访问的时间顺序赋予一个从 \\(1\\) 到 \\(N\\) 的编号，存储在
dfn数组中。 - 搜索树 (Search Tree)：以任意顶点为根，通过深度优先搜索构建的树。图中每个顶点仅被访问一次，所有在 DFS 过程中递归形成的边构成了搜索树。
- 追溯值 (Lowest Link Value)：用
low数组表示。定义为在以顶点 \\(x\\) 为根的子树（包括 \\(x\\) 本身）中，能够通过 至多一条 不在搜索树上的边（返祖边或横跨边）到达的、时间戳最小的顶点的dfn值。 - 点双连通图 (Biconnected Graph)：一张不存在割点的无向连通图。
- 点双连通分量 (Vertex-Biconnected Component, v-DCC)：无向连通图的极大点双连通子图。
追溯值的计算方法
- 初始时，令
low[x] = dfn[x]。 - 若 \\(x\\) 是搜索树上顶点 \\(y\\) 的父节点，则更新
low[x] = min(low[x], low[y])。 - 若存在一条无向边 \\((x, y)\\) 且该边不在搜索树上（即 \\(y\\) 是 \\(x\\) 的祖先或已访问过的其他子树中的节点），则更新
low[x] = min(low[x], dfn[y])。
割点的判定方法 若顶点 \(x\) 满足以下任一条件，则 \(x\) 是割点：
- \\(x\\) 不是搜索树的根节点，且存在其至少一个子节点 \\(y\\) 满足
dfn[x] <= low[y]。 - \\(x\\) 是搜索树的根节点，且存在其至少两个子节点 \\(y_1, y_2\\) 满足
dfn[x] <= low[y1]和dfn[x] <= low[y2]。 原理说明：当dfn[x] <= low[y]时，意味着从顶点 \(y\) 及其子树出发，无法通过除 \(x\) 之外的任何顶点到达 \(x\) 的祖先节点。因此，如果删除 \(x\)，则 \(y\) 及其子树将与 \(x\) 的祖先节点断开连接。特殊地，对于根节点 \(x\)，其没有祖先节点。若存在两个子树（由两个满足条件的子节点 \(y_1, y_2\) 代表）在删除 \(x\) 后无法相互连通，则 \(x\) 是割点。
示例：P3388 【模板】割点（割顶）是一道典型的割点求解模板题。
参考实现 (割点)
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
const int MAXN = 20009;
const int MAXM = 100009;
struct Edge {
int to;
int next;
};
Edge edges[MAXM << 1];
int head[MAXN], edgeCount;
int dfn[MAXN], low[MAXN], timer;
bool isCutVertex[MAXN];
int cutVertexCount;
std::vector<int> adj[MAXN]; // Adjacency list for cleaner input processing
void addEdge(int u, int v) {
edges[++edgeCount].to = v;
edges[edgeCount].next = head[u];
head[u] = edgeCount;
}
void tarjanDFS(int u, int parent) {
int children = 0;
low[u] = dfn[u] = ++timer;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent) continue; // Skip parent in undirected graph traversal
if (dfn[v]) { // If v has been visited
low[u] = std::min(low[u], dfn[v]);
} else { // If v has not been visited
children++;
tarjanDFS(v, u);
low[u] = std::min(low[u], low[v]);
// Check for cut vertex condition
if (parent != -1 && low[v] >= dfn[u]) {
isCutVertex[u] = true;
}
}
}
// Special case for the root of the DFS tree
if (parent == -1 && children > 1) {
isCutVertex[u] = true;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
// Initialize DFS arrays and perform Tarjan's algorithm
timer = 0;
for (int i = 1; i <= n; ++i) {
dfn[i] = 0;
low[i] = 0;
isCutVertex[i] = false;
head[i] = 0; // Reset head for adjacency list representation if needed, or handle edge list directly
}
edgeCount = 0; // Reset edge counter
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjanDFS(i, -1); // -1 indicates no parent for the root
}
}
// Count and print cut vertices
cutVertexCount = 0;
for (int i = 1; i <= n; ++i) {
if (isCutVertex[i]) {
cutVertexCount++;
}
}
std::cout << cutVertexCount << std::endl;
for (int i = 1; i <= n; ++i) {
if (isCutVertex[i]) {
std::cout << i << " ";
}
}
std::cout << std::endl;
return 0;
}
点双连通分量的求法 一个割点可能属于多个点双连通分量。
- 如果图中存在孤立的顶点，则该孤立顶点本身构成一个点双连通分量。
- 如果不存在孤立顶点，则每个点双连通分量至少包含两个顶点。 求解步骤：
- 在 DFS 过程中，首次访问到顶点 \\(x\\) 时，将其压入一个辅助栈。
- 当满足条件
dfn[x] <= low[y]时（其中 \\(y\\) 是 \\(x\\) 的子节点），表示以 \\(y\\) 为根的子树与 \\(x\\) 的其他部分通过 \\(x\\) 连接。此时，以 \\(y\\) 为根的子树（包括 \\(y\\)）与 \\(x\\) 构成了一个点双连通分量。 - 从栈顶开始，不断弹出顶点，直到顶点 \\(y\\) 被弹出。所有被弹出的顶点，连同顶点 \\(x\\)，共同构成了一个点双连通分量。
示例：P8435 【模板】点双连通分量 是一个求解点双连通分量的模板题。
参考实现 (点双连通分量)
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
const int MAXN = 500009;
const int MAXM = 2000009;
struct Edge {
int to;
int next;
};
Edge edges[MAXM << 1];
int head[MAXN], edgeCount;
int dfn[MAXN], low[MAXN], timer;
int vertexStack[MAXN], stackTop;
std::vector<std::vector<int>> biconnectedComponents;
int componentCount;
void addEdge(int u, int v) {
edges[++edgeCount].to = v;
edges[edgeCount].next = head[u];
head[u] = edgeCount;
}
void tarjanDFS(int u, int parent) {
low[u] = dfn[u] = ++timer;
vertexStack[++stackTop] = u;
int children = 0; // Count children for root's cut vertex check (though not strictly needed for DCC extraction)
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent) continue;
if (dfn[v]) { // Visited node, potential back edge
low[u] = std::min(low[u], dfn[v]);
} else { // Unvisited node, tree edge
children++;
tarjanDFS(v, u);
low[u] = std::min(low[u], low[v]);
// Check for articulation point and extract BCC
if (low[v] >= dfn[u]) {
componentCount++;
biconnectedComponents.push_back(std::vector<int>());
int currentVertex;
do {
currentVertex = vertexStack[stackTop--];
biconnectedComponents[componentCount - 1].push_back(currentVertex);
} while (currentVertex != v);
biconnectedComponents[componentCount - 1].push_back(u); // Add the articulation point itself
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
if (u == v) continue; // Skip self-loops, they don't affect DCCs typically
addEdge(u, v);
addEdge(v, u);
}
// Initialize DFS arrays and perform Tarjan's algorithm
timer = 0;
stackTop = 0;
componentCount = 0;
for (int i = 1; i <= n; ++i) {
dfn[i] = 0;
low[i] = 0;
head[i] = 0; // Reset adjacency list heads
}
edgeCount = 0; // Reset edge counter
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjanDFS(i, 0); // Using 0 as a sentinel for parent, assuming node IDs are positive
}
}
// Output the number of biconnected components and their sizes/members
std::cout << componentCount << std::endl;
for (const auto& component : biconnectedComponents) {
std::cout << component.size() << " ";
for (int vertex : component) {
std::cout << vertex << " ";
}
std::cout << std::endl;
}
return 0;
}
