原题链接
先用(tarjan)找出所有(e-DCC)，并进行缩点，这时桥的数量即是缩点后树的边数。
然后对于每一个添边((x,y))的操作，如果(x,y)属于同一个(e-DCC)，那么桥的数量不变。
如果分别属于两个(e-DCC)，那么从(x)所在的(e-DCC)（设为(e[x])）到(y)所在的(e-DCC)（设为(e[y])）路径上的所有边全部都不再是桥，因为这些边和新添加的边形成了一个环，不再属于桥。
所以我们可以找出(LCA(e[x],e[y]))，并从(e[x])往上跳到(LCA)，并将路径上所有边标记，(e[y])同理，而原边数减去第一次获得标记的边的数量即是答案。
但分析时间复杂度后发现，一个一个点往上跳太慢了（理论上会(T)，但这题貌似数据水，可过）
这时可以用并查集进行路径压缩来优化，即将已经标记的边的子节点所在集合向它的父节点所在集合合并，这样在执行向上跳的操作时，中间已经被标记的边相当于被压缩成一个点，直接跳过。
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int fi[N], di[M << 1], ne[M << 1], cfi[N], cdi[M], cne[M], dfn[N], low[N], bl[N], fa[N], de[N], f[N][18], l, lc, e_DCC, gn, ti;
bool bg[M << 1];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline void add(int x, int y)
{
di[++l] = y;
ne[l] = fi[x];
fi[x] = l;
}
inline void add_c(int x, int y)
{
cdi[++lc] = y;
cne[lc] = cfi[x];
cfi[x] = lc;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
inline void sw(int &x, int &y)
{
int z = x;
x = y;
y = z;
}
inline int fin(int x)
{
if (!(fa[x] ^ x))
return x;
return fa[x] = fin(fa[x]);
}
void tarjan(int x, int la)
{
int i, y;
dfn[x] = low[x] = ++ti;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!dfn[y])
{
tarjan(y, i);
low[x] = minn(low[x], low[y]);
if (low[y] > dfn[x])
bg[i] = bg[i ^ 1] = 1;
}
else
if (i ^ la ^ 1)
low[x] = minn(low[x], dfn[y]);
}
}
void dfs(int x)
{
int i, y;
bl[x] = e_DCC;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!bl[y] && !bg[i])
dfs(y);
}
}
void dfs_2(int x, int fa)
{
int i, y;
for (i = 1; i <= gn; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (i = cfi[x]; i; i = cne[i])
{
y = cdi[i];
if (y ^ fa)
{
de[y] = de[x] + 1;
f[y][0] = x;
dfs_2(y, x);
}
}
}
int lca(int x, int y)
{
int i;
if (de[x] > de[y])
sw(x, y);
for (i = gn; ~i; i--)
if (de[f[y][i]] >= de[x])
y = f[y][i];
if (!(x ^ y))
return x;
for (i = gn; ~i; i--)
if (f[x][i] ^ f[y][i])
{
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
int jp(int x, int z)
{
int y, s = 0;
while (x ^ z && x ^ 1)
{
s++;
y = fin(f[x][0]);
fa[x] = y;
x = y;
}
return s;
}
int main()
{
int i, x, y, n, m, q, z, t = 0, s;
while (1)
{
t++;
n = re();
m = re();
if (!n && !m)
return 0;
memset(fi, 0, sizeof(fi));
memset(cfi, 0, sizeof(cfi));
memset(bg, 0, sizeof(bg));
memset(bl, 0, sizeof(bl));
memset(f, 0, sizeof(f));
memset(dfn, 0, sizeof(dfn));
l = lc = 1;
ti = e_DCC = 0;
for (i = 1; i <= m; i++)
{
x = re();
y = re();
add(x, y);
add(y, x);
}
tarjan(1, 0);
for (i = 1; i <= n; i++)
if (!bl[i])
{
e_DCC++;
dfs(i);
}
for (i = 2; i <= l; i += 2)
{
x = bl[di[i ^ 1]];
y = bl[di[i]];
if (x ^ y)
{
add_c(x, y);
add_c(y, x);
}
}
gn = log2(e_DCC);
s = lc >> 1;
de[1] = 1;
dfs_2(1, 0);
for (i = 1; i <= e_DCC; i++)
fa[i] = i;
q = re();
printf("Case %d:
", t);
while (q--)
{
x = bl[re()];
y = bl[re()];
if (x ^ y)
{
z = lca(x, y);
s -= jp(fin(x), z);
s -= jp(fin(y), z);
}
printf("%d
", s);
}
printf("
");
}
return 0;
}