这题有点东西。
方法是:
1 跑一遍边双,把桥标记出来。把每个节点的父亲标记好。
2 不用缩点,你没有看错。不用。
3 每次query找lca,用最朴素的方法,不是倍增。先把depth更深的一步一步爬到一样高,然后两个点点一起一步一步往上爬,过程就把中间遇到的桥标记去掉。
4 路径压缩优化,就是其他题解的并查集,并不用真的开一并查集的数据结构。思想是在
找往上爬的过程中,把路径上的每一点的父节点都设为lca,这样下一次就不用看这些走过的边了。这个思路真妙。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 100010;
const int M = 400010;
int adjList[N], e[M], ne[M], idx;
int n, m, q;
int dfn[N], low[N], isce[N], id;
int fa[N], depth[N];
int ans;
void add(int a, int b) {
e[idx] = b;
ne[idx] = adjList[a];
adjList[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++id;
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa[u])
continue;
if (!dfn[v]) {
fa[v] = u;
depth[v] = depth[u] + 1;
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] == dfn[v] && !isce[v])
isce[v] = 1, ans++;
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
void lca(int a, int b) {
if (depth[a] < depth[b])
swap(a, b);
vector<int> vec;
while (depth[a] > depth[b]) {
if (isce[a]) {
isce[a] = 0;
ans--;
}
vec.push_back(a);
a = fa[a];
}
while (a != b) {
if (isce[a]) {
isce[a] = 0;
ans--;
}
if (isce[b]) {
isce[b] = 0;
ans--;
}
vec.push_back(a);
vec.push_back(b);
a = fa[a];
b = fa[b];
}
for (int v : vec)
fa[v] = a;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int caseNum = 1;
while(1) {
cin >> n >> m;
if (m == 0 && n == 0)
break;
memset(adjList, -1, sizeof adjList);
memset(e, 0, sizeof e);
memset(ne, 0, sizeof ne);
idx = 0;
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(fa, 0, sizeof fa);
memset(isce, 0, sizeof isce);
memset(depth, 0, sizeof depth);
id = 0;
ans = 0;
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
tarjan(1);
cout << "Case " << caseNum++ << ":" << endl;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
lca(a, b);
cout << ans << endl;
}
cout << endl;
}
return 0;
}