题目描述
给定一个 N 个点 M 条边的初始无向连通图。接下来有 Q 次操作，每次操作向图中添加一条边。每次添加边后，需要回答当前图中“桥”的数量。
桥 (Bridge)：在无向图中，如果移除一条边会使得图的连通分量数量增加，那么这条边被称为桥。
样例
输入样例：
3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0
输出样例：
Case 1:
1
0
Case 2:
2
0
(样例解释)
-
Case 1:
- 初始图: 1-2, 2-3. 边 (1,2) 和 (2,3) 都是桥。总共 2 个桥。 注意：这里与官方样例输出不符，初始时应该是2个桥。代码的逻辑是先构建初始图，然后计算一次EBCC和桥，再处理Q个查询。第一次查询是在加第一条边 之后。
- 初始图：1-2, 2-3。桥：(1,2), (2,3)。数量=2。
- 加边 (1, 2): 图中有重边 1-2。桥仍然是 (1,2) 和 (2,3)。但严格来说，如果存在另一条路径，桥就不再是桥。这里路径1-2-3存在。路径1-2本身存在。路径1-2存在。路径1-2-1, 1-3-2 都不是简单路径。添加(1,2)后，原有的 (1,2) 不再是桥了，因为有另一条路径 1-3-2。 等等，样例1的初始边是 1-2, 2-3。
- Corrected Case 1 Walkthrough:
- 初始图: 1-2, 2-3. 桥: (1,2), (2,3). 初始桥数 = 2.
- 查询 1: 加边 (1, 2). 图变为 1=2, 2-3. 边 (1,2) 现在有两条。 1和2之间现在有两条边，它们形成了一个环。所以 (1,2) 不再是桥。边 (2,3) 仍然是桥，因为删除它会使 3 与 {1, 2} 分离。 桥数 = 1. (输出 1)
- 查询 2: 加边 (1, 3). 图变为 1=2, 2-3, 1-3. 现在 1, 2, 3 形成了一个环 (1-2-3-1)。没有任何边是桥了。 桥数 = 0. (输出 0)
-
Case 2:
- 初始图: 1-2 (两条), 2-3, 1-4. 节点1和2本身就在一个边双连通分量里。边 (2,3) 是桥，边 (1,4) 是桥。 初始桥数 = 2.
- 查询 1: 加边 (1, 2). 又加了一条 1-2 的边。桥结构不变。 桥数 = 2. (输出 2)
- 查询 2: 加边 (3, 4). 图变为 1=2 (三条), 2-3, 1-4, 3-4. 现在有路径 2-3-4-1-2，所有点都在一个大的边双连通分量里。 桥数 = 0. (输出 0)
(注：根据代码的逻辑和标准题目流程，输出是 加边之后 的桥数量。)
核心思路：边双连通分量 (EBCC) 与 缩点
解决这类动态加边并查询桥数量的问题，关键在于理解加边操作对桥的影响。
-
桥与边双连通分量 (EBCC)：
- 一个图中的所有桥，将图分割成若干个部分。每个部分内部，任意两点之间都至少存在两条边不相交的路径。这样的极大子图被称为 边双连通分量 (Edge Biconnected Component, EBCC)。
- 一条边是桥，当且仅当它不属于任何一个环。
- 将图中的每个 EBCC 收缩成一个点（缩点），将连接不同 EBCC 的桥作为新图中的边。这样得到的 新图一定是一棵树（或者森林，但本题保证初始连通，所以是树）。这棵树通常被称为 块-割点树 或 Bridge Tree。
- 原图中的桥的数量，就等于这棵 Bridge Tree 的边数。
-
加边的影响：
- 向原图中添加一条边 (u,v)。
- 找到 u 和 v 分别所属的 EBCC，记为 ebcc(u) 和 ebcc(v)。
- Case 1: ebcc(u)==ebcc(v)
- u 和 v 已经在同一个 EBCC 中。这意味着 u 和 v 之间原本就存在至少两条边不相交的路径。
- 新加的边 (u,v) 只是在同一个 EBCC 内部增加了一条边，它会立刻成为某个环的一部分。
- 这条新边不会是桥，也不会影响任何现有的桥。
- 因此，桥的数量不变。
- Case 2: ebcc(u)≠ebcc(v)
- u 和 v 分属于不同的 EBCC。
- 在 Bridge Tree 中，找到 ebcc(u) 和 ebcc(v) 对应的两个节点。因为 Bridge Tree 是一棵树，这两个节点之间存在一条 唯一 的简单路径。
- 原图中添加边 (u,v)，相当于在 Bridge Tree 中 ebcc(u) 和 ebcc(v) 对应的节点之间添加了一条“快捷方式”。
- 这条新加的边 (u,v) 与 Bridge Tree 上 ebcc(u) 到 ebcc(v) 的路径，共同在原图中形成了一个 新的大环。
- 这个新环覆盖了 Bridge Tree 路径上的所有 边 (这些边对应原图的桥)。
- 因此，Bridge Tree 路径上的所有边，都不再是原图的桥了。
- 桥的数量减少，减少的数量等于 Bridge Tree 上 ebcc(u) 到 ebcc(v) 路径的 边数。
- 同时，这条路径上的所有 EBCC（以及新加的边）现在合并成了一个 新的、更大的 EBCC。
算法设计：Tarjan + Bridge Tree + HLD + Segment Tree
基于上述分析，我们可以设计出如下算法：
-
预处理 (处理初始图)：
- 使用 Tarjan 算法 找到初始图的所有 EBCC 和桥。
dfn[u]: 时间戳low[u]: u 能通过返祖边或树边到达的最小时间戳- 边 (u,v) (假设 dfn[u]<dfn[v]) 是桥当且仅当
low[v] > dfn[u]。 - Tarjan 算法也能同时将每个点划分到其所属的 EBCC (
bel[u]数组)。
- 构建 Bridge Tree：
- 令 EBCC 的数量为
k。创建一个k个节点的新图。 - 遍历原图中的所有 桥 (u,v)。在新图中添加一条连接
bel[u]和bel[v]的边。注意去重，因为多个桥可能连接相同的两个 EBCC（虽然在本题模型下不会，因为 EBCC 是极大子图）。 - 记录初始的桥数量
nb（即 Bridge Tree 的边数）。
- 令 EBCC 的数量为
- 使用 Tarjan 算法 找到初始图的所有 EBCC 和桥。
-
动态维护桥数量：
- 我们需要在 Bridge Tree 上高效地执行 “查询路径上的边数” 和 “将路径上的边标记为非桥” 的操作。
- 树链剖分 (Heavy-Light Decomposition, HLD) 是处理树上路径问题的有力工具。对 Bridge Tree 进行 HLD。
- 使用 线段树 (Segment Tree) 维护 HLD 后的序列。
- 将 Bridge Tree 的边映射到 HLD 序列上。通常，将树边 (p,c) (p 是 c 的父节点) 的状态 (是否为桥) 存储在线段树中
in[c]的位置 (in[c]是 HLD 剖分后 c 的 DFS 序入时间)。 - 线段树的每个节点维护一个区间内的 当前桥的数量 (sum)。
- 线段树需要支持：
- 区间查询 (Range Query): 查询一个区间内桥的数量 (求和)。
- 区间修改 (Range Apply/Update): 将一个区间内的所有边的状态修改为 “非桥” (将对应位置的值设为 0)。由于是区间修改，需要 懒惰标记 (Lazy Propagation)。
- 将 Bridge Tree 的边映射到 HLD 序列上。通常，将树边 (p,c) (p 是 c 的父节点) 的状态 (是否为桥) 存储在线段树中
-
处理查询：
- 对于每次加边操作 (A,B)：
- 获取 A 和 B 对应的 EBCC 编号:
x = bel[A-1],y = bel[B-1](注意 0-based/1-based 转换)。 - 如果
x == y，桥的数量不变，直接输出当前的nb。 - 如果
x != y：- 在 Bridge Tree (已经 HLD 处理过) 上找到
x和y的 最近公共祖先 (LCA)，记为l = h.lca(x, y)。 - 路径 x⇝ 由 x \leadsto l 和 y \leadsto l 两部分组成。
- 查询并修改：使用 HLD 的路径查询/修改功能，配合线段树：
- 查询路径 x \leadsto l 上的桥数量 (线段树区间查询)，并将这些桥在线段树中标记为 0 (线段树区间修改)。
- 查询路径 y \leadsto l 上的桥数量，并将这些桥在线段树中标记为 0。
- 设两次查询得到的桥数量总和为
removed_count。
- 更新总数：
nb = nb - removed_count。 - 输出当前的
nb。
- 在 Bridge Tree (已经 HLD 处理过) 上找到
- 获取 A 和 B 对应的 EBCC 编号:
- 对于每次加边操作 (A,B)：
实现细节与 C++ 代码解析
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// 全局集合，用于存储 EBCC（边双连通分量）算法中使用的边
std::set<std::pair<int, int>> E;
// EBCC 结构体，用于在无向图中查找边双连通分量和桥
struct EBCC {
int n; // 图中的节点数
std::vector<std::vector<int>> adj; // 图的邻接表表示
std::vector<int> stk; // DFS 过程中用于跟踪节点的栈
std::vector<int> dfn, low, bel; // DFS 编号、最低可达 DFS 编号和所属分量 ID
int cur, cnt; // 当前 DFS 时间戳和边双连通分量的数量
EBCC() {} // 默认构造函数
EBCC(int n) { // 带参数的构造函数，初始化图的大小
init(n);
}
// 初始化函数，设置图的大小并清空相关数据结构
void init(int n) {
this->n = n;
adj.assign(n, {}); // 初始化邻接表，每个节点为空向量
dfn.assign(n, -1); // DFS 编号初始化为 -1，表示未访问
low.resize(n); // 最低可达 DFS 编号数组
bel.assign(n, -1); // 所属分量 ID 初始化为 -1，表示未分配
stk.clear(); // 清空栈
cur = cnt = 0; // 初始化时间戳和分量计数器
}
// 添加无向边到图中
void addEdge(int u, int v) {
adj[u].push_back(v); // 在 u 的邻接表中添加 v
adj[v].push_back(u); // 在 v 的邻接表中添加 u（无向图）
}
// DFS 遍历以识别边双连通分量和桥
void dfs(int x, int p) {
dfn[x] = low[x] = cur++; // 设置当前节点的 DFS 编号和最低可达编号
stk.push_back(x); // 将当前节点压入栈中
for (auto y : adj[x]) { // 遍历当前节点的所有邻居
if (y == p) { // 跳过父节点，避免回边
continue;
}
if (dfn[y] == -1) { // 如果邻居未被访问
E.emplace(x, y); // 记录边 (x, y) 为树边
dfs(y, x); // 递归访问邻居
low[x] = std::min(low[x], low[y]); // 更新 x 的最低可达编号
} else if (bel[y] == -1 && dfn[y] < dfn[x]) { // 如果邻居已访问但未分配分量，且是回边
E.emplace(x, y); // 记录回边
low[x] = std::min(low[x], dfn[y]); // 更新最低可达编号
}
}
// 如果当前节点的 DFS 编号等于最低可达编号，则是一个割点或分量根
if (dfn[x] == low[x]) {
int y;
do {
y = stk.back(); // 从栈顶取节点
bel[y] = cnt; // 分配当前分量 ID
stk.pop_back(); // 弹出栈顶节点
} while (y != x); // 直到弹出当前节点 x，完成一个分量
cnt++; // 分量计数器加 1
}
}
// 执行 EBCC 算法，返回每个节点所属的分量 ID
std::vector<int> work() {
dfs(0, -1); // 从节点 0 开始 DFS，父节点设为 -1
return bel; // 返回分量 ID 数组
}
// 压缩后的图结构体，表示树结构
struct Graph {
int n; // 压缩后的节点数（分量数）
std::vector<std::pair<int, int>> edges; // 压缩图中的边
std::vector<int> siz; // 每个分量的大小（节点数）
std::vector<int> cnte; // 每个分量的内部边数
};
// 将原图压缩为树结构，去除桥并构建分量之间的关系
Graph compress() {
Graph g;
g.n = cnt; // 压缩图的节点数为分量数
g.siz.resize(cnt); // 初始化分量大小数组
g.cnte.resize(cnt); // 初始化分量内部边数数组
for (int i = 0; i < n; i++) { // 遍历所有原始节点
g.siz[bel[i]]++; // 统计每个分量的大小
for (auto j : adj[i]) { // 遍历每个节点的邻居
if (bel[i] < bel[j]) { // 如果属于不同分量，记录边
g.edges.emplace_back(bel[i], bel[j]);
} else if (i < j) { // 如果在同一分量内，统计内部边数
g.cnte[bel[i]]++;
}
}
}
return g;
}
};
// HLD 结构体，用于重链剖分（Heavy-Light Decomposition）
struct HLD {
int n; // 图中的节点数
std::vector<int> siz, top, dep, parent, in, out, seq; // 重链剖分相关数组
std::vector<std::vector<int>> adj; // 邻接表表示
int cur; // 当前时间戳
HLD() {}
HLD(int n) {
init(n);
}
// 初始化函数
void init(int n) {
this->n = n;
siz.resize(n); // 子树大小
top.resize(n); // 链顶节点
dep.resize(n); // 节点深度
parent.resize(n); // 父节点
in.resize(n); // DFS 进入时间
out.resize(n); // DFS 离开时间
seq.resize(n); // DFS 序列
cur = 0; // 初始化时间戳
adj.assign(n, {}); // 初始化邻接表
}
// 添加无向边
void add(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// 执行重链剖分
void work(int root = 0) {
top[root] = root; // 设置根节点的链顶为自己
dep[root] = 0; // 根节点深度为 0
parent[root] = -1; // 根节点无父节点
dfs1(root); // 第一次 DFS 计算子树大小
dfs2(root); // 第二次 DFS 分配链
}
// 第一次 DFS，计算子树大小并调整重儿子
void dfs1(int u) {
if (parent[u] != -1) { // 如果不是根节点
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u])); // 删除父节点边
}
siz[u] = 1; // 当前节点计入子树大小
for (auto &v : adj[u]) { // 遍历所有子节点
parent[v] = u; // 设置父节点
dep[v] = dep[u] + 1; // 子节点深度加 1
dfs1(v); // 递归处理子节点
siz[u] += siz[v]; // 累加子树大小
if (siz[v] > siz[adj[u][0]]) { // 如果当前子节点更大，设为重儿子
std::swap(v, adj[u][0]);
}
}
}
// 第二次 DFS，分配链和时间戳
void dfs2(int u) {
in[u] = cur++; // 记录进入时间
seq[in[u]] = u; // 记录 DFS 序列
for (auto v : adj[u]) { // 遍历所有子节点
top[v] = v == adj[u][0] ? top[u] : v; // 重儿子延续链，轻儿子新建链
dfs2(v); // 递归处理子节点
}
out[u] = cur; // 记录离开时间
}
// 计算两个节点的最近公共祖先（LCA）
int lca(int u, int v) {
while (top[u] != top[v]) { // 当不在同一条链上
if (dep[top[u]] > dep[top[v]]) { // 将深度较大的节点向上跳
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v; // 返回深度较小的节点作为 LCA
}
// 计算两个节点之间的距离
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)]; // 距离公式
}
// 从节点 u 向上跳 k 步
int jump(int u, int k) {
if (dep[u] < k) { // 如果深度不足，返回 -1
return -1;
}
int d = dep[u] - k; // 目标深度
while (dep[top[u]] > d) { // 当链顶深度大于目标深度
u = parent[top[u]]; // 跳到上一条链
}
return seq[in[u] - dep[u] + d]; // 根据 DFS 序列返回目标节点
}
// 判断 u 是否是 v 的祖先
bool isAncester(int u, int v) {
return in[u] <= in[v] && in[v] < out[u]; // 通过时间戳判断
}
// 在根为 u 的树中，找到 v 的父节点
int rootedParent(int u, int v) {
std::swap(u, v); // 交换参数以匹配定义
if (u == v) { // 如果相同，返回自身
return u;
}
if (!isAncester(u, v)) { // 如果 u 不是 v 的祖先，返回 v 的父节点
return parent[u];
}
auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
return in[x] < in[y]; // 查找 v 的直接子节点
}) - 1;
return *it; // 返回 v 的父节点
}
// 在根为 u 的树中，计算 v 的子树大小
int rootedSize(int u, int v) {
if (u == v) { // 如果相同，返回整个树的大小
return n;
}
if (!isAncester(v, u)) { // 如果 v 不是 u 的祖先，返回 v 的子树大小
return siz[v];
}
return n - siz[rootedParent(u, v)]; // 否则返回剩余部分的大小
}
// 在根为 a 的树中，计算 b 和 c 的 LCA
int rootedLca(int a, int b, int c) {
return lca(a, b) ^ lca(b, c) ^ lca(c, a); // 使用异或运算计算
}
};
// 懒惰标记线段树模板
template<class Info, class Tag>
struct LazySegmentTree {
int n; // 线段树的大小
std::vector<Info> info; // 节点信息
std::vector<Tag> tag; // 懒惰标记
LazySegmentTree() {}
LazySegmentTree(int n) {
init(n);
}
template<class T>
LazySegmentTree(std::vector<T> w) {
init(w);
}
// 初始化线段树
void init(int n) {
this->n = n;
info.resize(4 << std::__lg(n)); // 分配足够的空间（4 倍 log n）
tag.resize(4 << std::__lg(n)); // 同上
}
// 用初始值向量初始化线段树
template<class T>
void init(std::vector<T> w) {
init(w.size());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) { // 叶子节点
info[p] = w[l];
return;
}
int m = (l + r) / 2; // 分割点
build(2 * p, l, m); // 递归构建左子树
build(2 * p + 1, m, r); // 递归构建右子树
pull(p); // 更新当前节点信息
};
build(1, 0, n); // 从根节点开始构建
}
// 从子节点更新父节点信息
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
// 应用懒惰标记到当前节点
void apply(int p, const Tag &v) {
info[p].apply(v); // 更新节点信息
tag[p].apply(v); // 更新懒惰标记
}
// 将懒惰标记下推到子节点
void push(int p) {
apply(2 * p, tag[p]); // 左子节点应用标记
apply(2 * p + 1, tag[p]); // 右子节点应用标记
tag[p] = Tag(); // 清空当前节点的标记
}
// 修改单个节点的值
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) { // 叶子节点
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p); // 下推标记
if (x < m) { // 修改左子树
modify(2 * p, l, m, x, v);
} else { // 修改右子树
modify(2 * p + 1, m, r, x, v);
}
pull(p); // 更新当前节点
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v); // 从根节点开始修改
}
// 查询区间 [x, y) 的信息
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) { // 区间无交集
return Info();
}
if (l >= x && r <= y) { // 区间完全包含
return info[p];
}
int m = (l + r) / 2;
push(p); // 下推标记
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y); // 合并左右子树结果
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r); // 从根节点开始查询
}
// 在区间 [x, y) 上应用懒惰标记
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) { // 区间无交集
return;
}
if (l >= x && r <= y) { // 区间完全包含
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p); // 下推标记
rangeApply(2 * p, l, m, x, y, v); // 处理左子树
rangeApply(2 * p + 1, m, r, x, y, v); // 处理右子树
pull(p); // 更新当前节点
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v); // 从根节点开始应用
}
// 查找第一个满足条件的节点
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) { // 区间无交集或条件不满足
return -1;
}
if (r - l == 1) { // 叶子节点
return l;
}
int m = (l + r) / 2;
push(p); // 下推标记
int res = findFirst(2 * p, l, m, x, y, pred); // 先查左子树
if (res == -1) { // 如果左子树无结果，查右子树
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 0, n, l, r, pred); // 从根节点开始查找
}
// 查找最后一个满足条件的节点
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) { // 区间无交集或条件不满足
return -1;
}
if (r - l == 1) { // 叶子节点
return l;
}
int m = (l + r) / 2;
push(p); // 下推标记
int res = findLast(2 * p + 1, m, r, x, y, pred); // 先查右子树
if (res == -1) { // 如果右子树无结果，查左子树
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
return findLast(1, 0, n, l, r, pred); // 从根节点开始查找
}
};
// 懒惰标记的定义
struct Tag {
int v = -1; // 标记值，-1 表示无标记
void apply(const Tag &t) { // 应用标记
if (t.v != -1) v = t.v; // 如果新标记有效，更新当前标记
}
};
// 线段树节点信息的定义
struct Info {
int sum = 0; // 区间和
void apply(const Tag &t) { // 应用标记到信息
if (t.v != -1) sum = t.v; // 如果标记有效，更新和
}
};
// 定义信息合并操作
auto operator+(const Info &a, const Info &b) -> Info {
return {a.sum + b.sum}; // 返回两个区间的和
}
// 主函数
int main() {
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(nullptr);
int n, m, c = 0; // n: 节点数, m: 边数, c: 测试用例编号
while (cin >> n >> m && (n || m)) { // 读取多组测试用例，直到 n 和 m 均为 0
cout << "Case " << ++c << ":\n"; // 输出测试用例编号
EBCC ebcc(n); // 创建 EBCC 对象
vector<pair<int, int>> e(m); // 存储输入的边
for (int i = 0; i < m; i++) { // 读取 m 条边
int u, v;
cin >> u >> v;
u--; v--; // 输入从 1 开始，转换为 0-based
ebcc.addEdge(u, v); // 添加边到 EBCC
e[i] = {u, v}; // 保存原始边
}
auto bel = ebcc.work(); // 执行 EBCC 算法，获取每个节点的分量 ID
int k = ebcc.cnt; // 分量数量
HLD h(k); // 创建 HLD 对象，基于分量数
set<pair<int, int>> br; // 存储桥（不同分量之间的边）
for (auto [u, v] : e) { // 遍历所有边
if (bel[u] != bel[v]) { // 如果边连接不同分量
int a = bel[u], b = bel[v];
if (a > b) swap(a, b); // 确保 a < b，避免重复
if (!br.count({a, b})) { // 如果边未记录
br.emplace(a, b); // 记录桥
h.add(a, b); // 添加到 HLD 的树中
}
}
}
if (k) h.work(0); // 如果有分量，执行重链剖分
vector<Info> val(k); // 线段树初始值数组
int nb = 0; // 桥的数量
if (k > 1) { // 如果有多个分量
for (auto [u, v] : br) { // 遍历所有桥
int c = h.dep[u] > h.dep[v] ? u : v; // 选择深度较大的节点
val[h.in[c]] = {1}; // 在线段树中标记为 1
nb++; // 桥计数加 1
}
}
LazySegmentTree<Info, Tag> t(val); // 创建懒惰标记线段树
// 计算从 u 到 a 的路径上的桥数量，并更新标记
auto path = [&](int u, int a, LazySegmentTree<Info, Tag> &t) -> int {
int res = 0;
while (u != a && u != -1) { // 当 u 未到达 a
if (h.top[u] == h.top[a]) { // 如果在同一条链上
int s = h.in[a] + 1, e = h.in[u];
if (s <= e) { // 查询并清零区间
res += t.rangeQuery(s, e + 1).sum;
t.rangeApply(s, e + 1, {0});
}
u = a; // 到达目标
} else { // 如果不在同一条链上
int s = h.in[h.top[u]], e = h.in[u];
if (s <= e) { // 查询并清零区间
res += t.rangeQuery(s, e + 1).sum;
t.rangeApply(s, e + 1, {0});
}
u = h.parent[h.top[u]]; // 跳到上一条链
}
}
return res; // 返回路径上的桥数量
};
int q; // 查询次数
cin >> q;
while (q--) { // 处理每个查询
int a, b;
cin >> a >> b;
a--; b--; // 转换为 0-based
int x = bel[a], y = bel[b]; // 获取 a 和 b 的分量 ID
if (x != y && k >= 2) { // 如果不在同一分量且至少有两个分量
int l = h.lca(x, y); // 计算 LCA
if (l != -1) nb -= (path(x, l, t) + path(y, l, t)); // 更新桥数量
if (nb < 0) nb = 0; // 确保桥数量非负
}
cout << nb << "\n";
}
cout << "\n";
}
return 0;
}
时间复杂度
-
预处理：
- Tarjan 找 EBCC: O(N + M)
- 建 Bridge Tree: 遍历初始边 O(M)，加边 O(k) (k 为 EBCC 数, k \le N)
- HLD: O(k)
- 建线段树: O(k)
- 总预处理: O(N + M)
-
查询处理：
- 每次查询 (A, B):
- 找 bel[A], bel[B]: O(1)
- LCA 计算: O(\log k)
- HLD 路径查询与修改: 每次涉及 O(\log k) 条重链，每条重链在线段树上是 O(\log k) 的操作。总共 O(\log^2 k)。 (如果线段树实现优秀，路径操作也可以做到 O(\log k))
- 总查询: O(Q \log^2 k) 或 O(Q \log k)。
- 每次查询 (A, B):
-
整体复杂度： O(N + M + Q \log^2 k) 或 O(N + M + Q \log k)。由于 k \le N，可以看作 O(N + M + Q \log^2 N) 或 O(N + M + Q \log N)。
考虑到 N=100000, M=200000, Q=1000，\log N \approx 17，\log^2 N \approx 289。
N+M \approx 300000。
Q \log^2 N \approx 1000 \times 289 \approx 289000。
Q \log N \approx 1000 \times 17 \approx 17000。
无论哪种复杂度，对于给定的数据范围都足够快。
思考与总结
- 核心转化: 将动态图的桥计数问题转化为静态树上的路径修改和全局查询问题。
- 关键工具: EBCC (缩点) + Bridge Tree + HLD + Segment Tree。
- 加边影响: 理解加边只会减少桥，并且减少的是新边连接的两个 EBCC 在 Bridge Tree 上路径的边。
- 实现细节: 注意 0-based/1-based 索引；正确地将树边映射到线段树节点；LCA 和 HLD 路径操作的正确性；线段树懒惰标记的实现。
- 复杂度: 该方法效率很高，适用于较大规模的数据。
