【双连通分量|【算法竞赛进阶指南】(图论) Network 边双连通分量】
文章图片
题意分析：
我们可以利用双连通分量e-dcc将图缩点变成一棵树， 树上的边即为桥的数量。
接着我们分析加边的操作：
- 如果两个点在一个双连通分量中，那么加边并不会影响当前桥的数量
- 如果两个点不在一个双连通分量中，那么会影响桥的数量。可以转换为在树上加一条边，那么必然会形成一个环，接着只需要对环上的边进行标记，标记数为减少的桥的数量。找环的操作可以先找到两点的lca然后往上便利并标记即可。复杂度为O(M+Q*N)，本题数据比较宽松，这样的作法可以直接过，当然也可以用并查集进行优化。
#include
using namespace std;
const int N = 2e5 + 10;
int n, m, low[N], dfn[N], idx, bridge[N<<1], cnt, c[N], scc, h[N], cnt2, h2[N], vis[N<<1], C;
int d[N], f[N][30], t, q;
struct edge {
int to, next;
}e[N << 1], e2[N << 1];
void add(int u, int v) {
e[cnt].to = v;
e[cnt].next = h[u];
h[u] = cnt++;
}void add_c(int u, int v) {
e2[cnt2].to = v;
e2[cnt2].next = h2[u];
h2[u] = cnt2++;
}void tarjan(int x, int in_edge) {
low[x] = dfn[x] = ++idx;
for (int i = h[x];
~i;
i = e[i].next) {
int v = e[i].to;
if (!dfn[v]) {
tarjan(v, i);
low[x] = min(low[x], low[v]);
if (low[v] > dfn[x]) bridge[i] = bridge[i ^ 1] = 1;
}
else if (i != (in_edge ^ 1))
low[x] = min(low[x], dfn[v]);
}
}void dfs(int x) {
c[x] = scc;
for (int i = h[x];
~i;
i = e[i].next) {
int v = e[i].to;
if (c[v] || bridge[i]) continue;
dfs(v);
}
}void bfs(int x) {
memset(d, 0, sizeof d);
memset(f, 0, sizeof f);
queue q;
q.push(x);
d[x] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = h2[u];
~i;
i = e2[i].next) {
int v = e2[i].to;
if (d[v]) continue;
d[v] = d[u] + 1;
f[v][0] = u;
for (int j = 1;
j <= t;
j++) {
f[v][j] = f[f[v][j - 1]][j - 1];
}
q.push(v);
}
}
}int lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = t;
i >= 0;
i--) if (d[f[y][i]] >= d[x]) y = f[y][i];
if (x == y) return x;
for (int i = t;
i >= 0;
i--) {
if (f[y][i] != f[x][i])
y = f[y][i], x = f[x][i];
}
return f[x][0];
}int find(int x, int p) {
int num = 0;
while (x != p) {
for (int i = h2[x];
~i;
i = e2[i].next) {
if (e2[i].to == f[x][0] && !vis[i]) vis[i] = 1, num++;
}
x = f[x][0];
}
return num;
}int main() {
ios::sync_with_stdio(0);
while (cin >> n >> m) {
if (n == 0 && m == 0) break;
printf("Case %d:\n", ++C);
memset(h, -1, sizeof h);
memset(h2, -1, sizeof h2);
memset(bridge, 0, sizeof bridge);
memset(c, 0, sizeof c);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
cnt = cnt2 = scc = idx = 0;
for (int i = 0;
i < m;
i++) {
int x, y;
cin >> x >> y;
add(x, y), add(y, x);
}
for (int i = 1;
i <= n;
i++) if (!dfn[i]) tarjan(i, 0);
for (int i = 1;
i <= n;
i++) {
if (!c[i]) {
++scc;
dfs(i);
}
}int bridge_now = 0;
for (int i = 0;
i < cnt;
i += 2) {
int u = e[i].to, v = e[i ^ 1].to;
if (c[u] == c[v]) continue;
add_c(c[u], c[v]), add_c(c[v], c[u]);
bridge_now++;
}t = (int)(log(scc) / log(2)) + 1;
bfs(1);
memset(vis, 0, sizeof vis);
cin >> q;
for (int i = 0;
i < q;
i++) {
int x, y;
cin >> x >> y;
if (c[x] == c[y]) {
printf("%d\n", bridge_now);
continue;
}
int p = lca(c[x], c[y]);
bridge_now -= find(c[x], p);
bridge_now -= find(c[y], p);
printf("%d\n", bridge_now);
}
printf("\n");
}
}
