网络
C++ 代码
/*
先求出所有边双连通分量,再对每个连通分量进行缩点,得到一颗新的树,最开始,树中边的数量就是桥的数量。
依次考虑每个添加边 (x, y) 的操作,若 x, y 属于同一个连通分量,桥的数量不变。
设 c[x] 表示节点 x 所在的连通分量编号。
若不属于同一个连通分量,则 c[x] 与 c[y] 之间的路径上的每条边都不再是桥,因为他们都处在一个环内。
可以求出 p = lca(c[x], c[y]),从 c[x] 不断走向父节点,直到 p,把经过的边都标记成不再是桥。同样,
从 c[y] 不断走向父节点,直到 p,把经过的边都标记成不在是桥。途中若有 cnt 条边新获得印记,则把途
中桥的总数减掉 cnt。
这样这道题的时间复杂度就是 O(m + q * n),已经够了。当然这里还能再做一步优化。
用并查集对不在是桥的边进行了路径压缩,时间复杂度降为 O(m + q * logn)
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 400010;
int n, m, q;
int h[N], e[M], ne[M], idx; //原树
int hc[N], ec[M], nc[M], idc; //新树
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt; //记录每个点的连通分量编号
int p[N]; //并查集
int dep[N], fa[N]; //dep[] 表示每个节点的深度,fa[] 表示每个连通分量在新树中的父节点
bool bridge[M]; //记录每条边是不是桥
void add(int a, int b) //原图添加边
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void add_c(int a, int b) //新图添加边
{
ec[idc] = b, nc[idc] = hc[a], hc[a] = idc++;
}
void tarjan(int u, int bri) //Tarjan求桥
{
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j, i);
low[u] = min(low[u], low[j]);
if(dfn[u] < low[j])
bridge[i] = bridge[i ^ 1] = true;
}
else if(i != (bri ^ 1))
low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u]) //找到一个新的连通分量
{
++dcc_cnt;
int y;
do
{
y = stk[top--];
id[y] = dcc_cnt;
} while(y != u);
}
}
void dfs(int u) //预处理新图中的 dep[], fa[]
{
for(int i = hc[u]; i != -1; i = nc[i])
{
int j = ec[i];
if(!dep[j])
{
dep[j] = dep[u] + 1;
fa[j] = u;
dfs(j);
}
}
}
int find(int x) //并查集
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
int T = 1;
while(scanf("%d%d", &n, &m), n || m)
{
//初始化
memset(h, -1, sizeof h);
memset(hc, -1, sizeof hc);
memset(dfn, 0, sizeof dfn);
memset(bridge, 0, sizeof bridge);
memset(id, 0, sizeof id);
memset(dep, 0, sizeof dep);
timestamp = idx = idc = dcc_cnt = top = 0;
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a); //无向边
}
tarjan(1, -1); //求桥
for(int i = 0; i < idx; i++) //构建新图
{
int x = e[i ^ 1], y = e[i];
if(id[x] == id[y]) continue; //同一连通分量内的边跳过
add_c(id[x], id[y]), add_c(id[y], id[x]); //两个连通分量之间的边加上
}
int res = dcc_cnt - 1; //当前答案 = 新图中边的数量 = 新图中节点数量 - 1
dep[1] = 1; //设 1 号连通分量为根节点
dfs(1); //预处理 dep[], fa[]
for(int i = 1; i <= dcc_cnt; i++) p[i] = i; //初始化并查集
printf("Case %d:\n", T++);
scanf("%d", &q);
while(q--)
{
int x, y;
scanf("%d%d", &x, &y);
x = id[x], y = id[y];
if(x != y) //在两个连通分量之间加边,才会改变桥的数量
{
x = find(x), y = find(y);
while(x != y) //将 x 和 y 到 lca(x, y) 之间的所有桥改为非桥
{
if(dep[x] < dep[y]) swap(x, y); //保证 dep[x] >= dep[y]
if(!dep[x]) break; //深度为0,说明遍历到头了,直接弹出
p[x] = find(fa[x]); //将 x 到 fa[x] 之间的桥改为非桥,即将让这条边消失,让 x 指向fa[fa[x]]
res--; //桥的数量 - 1
x = find(x); //向上走
}
}
printf("%d\n", res);
}
puts("");
}
return 0;
}