Problem Description
City C is really a nightmare of all drivers for its traffic jams. To solve the traffic problem, the mayor plans to build a RTQS (Real Time Query System) to monitor all traffic situations. City C is made up of N crossings and M roads, and each road connects two crossings. All roads are bidirectional. One of the important tasks of RTQS is to answer some queries about route-choice problem. Specifically, the task is to find the crossings which a driver MUST pass when he is driving from one given road to another given road.
Input
There are multiple test cases.
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi).
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: 0<N<=10000, 0<M<=100000, 0<Q<=10000, 0<Xi,Yi<=N, 0<S,T<=M
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi).
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: 0<N<=10000, 0<M<=100000, 0<Q<=10000, 0<Xi,Yi<=N, 0<S,T<=M
Output
For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.
题目大意：给一个N个点M条边的无向图，然后有Q个询问X，Y，问第X条边到第Y条边必需要经过的点有多少个。
思路：对于两条边X，Y，若他们在同一个双连通分量中，那他们之间至少有两条路径可以互相到达。
那么，对于两条不在同一个分量中的边X，Y，显然从X到Y必须要经过的的点的数目等于从X所在的边双连通分量到Y所在的双连通分量中的割点的数目。
于是，可以找出所有双连通分量，缩成一个点。对于 双连通分量A - 割点 - 双连通分量B，重构图成3个点 A - 割点 - B。
那么，所有的双连通分量缩完之后，新图G‘成了一棵树（若存在环，那么环里的点都在同一个双连通分量中，矛盾）
那么题目变成了：从X所在的G'中的点，到Y所在的G’中的点的路径中，有多少点是由割点变成的。
由于图G‘中的点都是 双连通分量 - 割点 - 双连通分量 - 割点 - 双连通分量……的形式（两个双连通分量不会连在一起）
那么X到Y的割点的数目就等于两点距离除以2，暨(dep[x] + dep[Y] - dep[LCA(X, Y)]) / 2，其中dep是深度，lca是最近公共祖先。
其中LCA用tarjan也好，用RMQ也好，随意。我用的是离线的tarjan。
细节：因为找边双连通分量的思路错了跪了一整天……写一下正确又优美的姿势是怎么样的>_<
类似于tarjan求强联通的算法，用一个vis[]数组记录某条边是否被访问过。
每次第一次访问一条边，把这条边压入栈中，在遍历完某条边指向的点之后，若pre[u] <= lowlink[v]（见code），把栈中的边都设为同一个边双连通分量。
仔细想想觉得应该是对的。我不会证明>_<
PS：新图G’中点的数目可能会高达2*n的等级，试想一下原图恰好是一条链的情况，由于存在重边，边数也最好要2*m。
代码（178MS）：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL; typedef pair<int, int> PII; const int MAXV = ;
const int MAXE = ; int ans[MAXV];
vector<PII> query[MAXV << ]; struct SccGraph {
int head[MAXV << ], fa[MAXV << ], ecnt;
bool vis[MAXV << ];
int to[MAXE << ], next[MAXE << ];
int dep[MAXV << ]; void init(int n) {
memset(head, -, sizeof(int) * (n + ));
memset(vis, , sizeof(bool) * (n + ));
for(int i = ; i <= n; ++i) fa[i] = i;
ecnt = ;
} int find_set(int x) {
return fa[x] == x ? x : fa[x] = find_set(fa[x]);
} void add_edge(int u, int v) {
to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++;
} void lca(int u, int f, int deep) {
dep[u] = deep;
for(int p = head[u]; ~p; p = next[p]) {
int &v = to[p];
if(v == f || vis[v]) continue;
lca(v, u, deep + );
fa[v] = u;
}
vis[u] = true;
for(vector<PII>::iterator it = query[u].begin(); it != query[u].end(); ++it) {
if(vis[it->first]) {
ans[it->second] = (dep[u] + dep[it->first] - * dep[find_set(it->first)]) / ;
}
}
}
} G; int head[MAXV], lowlink[MAXV], pre[MAXV], ecnt, dfs_clock;
int sccno[MAXV], scc_cnt;
int to[MAXE], next[MAXE], scc_edge[MAXE];
bool vis[MAXE], iscut[MAXV];
int stk[MAXE], top;
int n, m, q; void init() {
memset(head, -, sizeof(int) * (n + ));
memset(pre, , sizeof(int) * (n + ));
memset(iscut, , sizeof(bool) * (n + ));
memset(vis, , sizeof(bool) * ( * m));
ecnt = scc_cnt = dfs_clock = ;
} void add_edge(int u, int v) {
to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++;
} void tarjan(int u, int f) {
pre[u] = lowlink[u] = ++dfs_clock;
int child = ;
for(int p = head[u]; ~p; p = next[p]) {
if(vis[p]) continue;
vis[p] = vis[p ^ ] = true;
stk[++top] = p;
int &v = to[p];
if(!pre[v]) {
++child;
tarjan(v, u);
lowlink[u] = min(lowlink[u], lowlink[v]);\
if(pre[u] <= lowlink[v]) {
iscut[u] = true;
++scc_cnt;
while(true) {
int t = stk[top--];
scc_edge[t] = scc_edge[t ^ ] = scc_cnt;
if(t == p) break;
}
}
} else lowlink[u] = min(lowlink[u], pre[v]);
}
if(f < && child == ) iscut[u] = false;
} void build() {
G.init(scc_cnt);
for(int p = ; p != ecnt; ++p) {
int &v = to[p];
if(iscut[v]) G.add_edge(sccno[v], scc_edge[p]);
}
} void solve() {
for(int i = ; i <= n; ++i)
if(!pre[i]) tarjan(i, );
for(int u = ; u <= n; ++u)
if(iscut[u]) sccno[u] = ++scc_cnt;
} int main() {
while(scanf("%d%d", &n, &m) != EOF) {
if(n == && m == ) break;
init();
for(int i = ; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
}
solve();
build();
for(int i = ; i <= scc_cnt; ++i) query[i].clear();
scanf("%d", &q);
for(int i = ; i < q; ++i) {
int x, y;
scanf("%d%d", &x, &y);
x = scc_edge[x * - ]; y = scc_edge[y * - ];
query[x].push_back(make_pair(y, i));
query[y].push_back(make_pair(x, i));
}
for(int i = ; i <= scc_cnt; ++i) if(!G.vis[i]) G.lca(i, , );
for(int i = ; i < q; ++i) printf("%d\n", ans[i]);
}
}