先用 Tarjan 建圆方树，再统计 x 到 y 在圆方树路径上经过了多少个原图割点。
OJ: luogu
题目 ID: P8604
难度:普及+/提高
标签:图论割点tarjan
日期: 2026-06-19 19:20
题意
给出一个无向图和两个点 x, y。
如果删掉某个点 z 之后，x 和 y 不再连通，那么 z 就是关于 x,y 的关键点。题目要求统计这样的关键点个数。
思路
最直接的办法是枚举每个点 z，删掉它后跑一次 BFS，看 x 和 y 是否还能连通。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> g;
bool disconnected_after_remove(int n, int x, int y, int ban) {
vector<int> vis(n + 1, 0);
queue<int> q;
q.push(x);
vis[x] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (v == ban || vis[v]) {
continue;
}
vis[v] = 1;
q.push(v);
}
}
return !vis[y];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.assign(n + 1, {});
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int x, y;
cin >> x >> y;
int ans = 0;
for (int z = 1; z <= n; ++z) {
if (z == x || z == y) {
continue;
}
if (disconnected_after_remove(n, x, y, z)) {
++ans;
}
}
cout << ans << '\n';
return 0;
}brute.cpp 适合小图对拍，但正式数据下没有利用图的结构。
这张图展示样例里的原图结构：
graph G {
1 -- 3;
2 -- 3;
3 -- 4;
3 -- 5;
4 -- 5;
5 -- 6;
}
从这张图里能直观看到：1 到 6 的所有通路都必须经过 3 和 5，所以答案是 2。
更系统的做法是：先用 Tarjan 求点双连通分量，再建圆方树。
- 原图点保留为圆点
- 每个点双新建一个方点
- 点属于哪个点双，就在圆方树里连边
建好之后，原图中任意两点 x, y 的连通结构会压缩成圆方树上的唯一一条路径。路径上出现的原图圆点（排除 x, y 自己）恰好就是把它们分开的关键点。
所以做法就是：
- Tarjan 建圆方树
- 在圆方树上找
x -> y路径 - 数这条路径上经过多少个原图点
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u;
int v;
};
static vector<vector<pair<int, int>>> g;
static vector<Edge> edges;
static vector<int> dfn, low;
static vector<int> estack;
static vector<vector<int>> tree;
static vector<int> mark;
static int n, m;
static int dfs_clock = 0;
static int bcc_cnt = 0;
void tarjan(int u, int parent_edge) {
dfn[u] = low[u] = ++dfs_clock;
for (auto [v, id] : g[u]) {
if (!dfn[v]) {
estack.push_back(id);
tarjan(v, id);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
++bcc_cnt;
int comp = n + bcc_cnt;
vector<int> nodes;
while (true) {
int eid = estack.back();
estack.pop_back();
int a = edges[eid].u;
int b = edges[eid].v;
if (!mark[a]) {
mark[a] = 1;
nodes.push_back(a);
}
if (!mark[b]) {
mark[b] = 1;
nodes.push_back(b);
}
if (eid == id) {
break;
}
}
for (int x : nodes) {
tree[comp].push_back(x);
tree[x].push_back(comp);
mark[x] = 0;
}
}
} else if (id != parent_edge && dfn[v] < dfn[u]) {
estack.push_back(id);
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
edges.resize(m);
tree.assign(n + m + 5, {});
mark.assign(n + 1, 0);
dfn.assign(n + 1, 0);
low.assign(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
g[u].push_back({v, i});
g[v].push_back({u, i});
}
int x, y;
cin >> x >> y;
if (x == y) {
cout << 0 << '\n';
return 0;
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i, -1);
}
}
int tot = n + bcc_cnt;
vector<int> parent(tot + 1, -1);
queue<int> q;
q.push(x);
parent[x] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == y) {
break;
}
for (int v : tree[u]) {
if (parent[v] != -1) {
continue;
}
parent[v] = u;
q.push(v);
}
}
if (parent[y] == -1) {
cout << 0 << '\n';
return 0;
}
int ans = 0;
int cur = y;
while (cur != x) {
if (cur <= n && cur != x && cur != y) {
++ans;
}
cur = parent[cur];
}
cout << ans << '\n';
return 0;
}复杂度
Tarjan 和最后的 BFS 都是线性复杂度，所以总时间复杂度是
总结
这题的关键是把“删掉某点后是否断开”转成“圆方树路径上有哪些割点”。一旦建出圆方树，答案就变成了很直接的路径计数。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
