题目
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.
输入格式
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 i th line (i starts from 1)contains two integers (X_i) and (Y_i), representing that road i connects crossing (X_i) and (Y_i) ((X_i≠Y_i)).
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 le 10000), (0 < M le 100000), (0 < Q le 10000), (0 < X_i),(Y_i le N), (0 < S,T le M)
输出格式
For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.
样例输入
5 6
1 2
1 3
2 3
3 4
4 5
3 5
2
2 3
2 4
0 0
样例输出
0
1
题解
题目大意:
输出两条边之间必须经过的点
这道题其实没有什么思维难度, 显然先缩点, 求lca即可.
主要就是调起来很麻烦, 而且起点和终点不是点是边.
tarjon缩点, 倍增求lca
代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5, M = 1e5 + 5, Lg = 25;
int n, m, qn, tot, head[2][N << 1], top, sta[N], dfsc, dfn[N], low[N], dccCnt, root, bel[N], eb[M], fa[N << 1][Lg], dep[N << 1], id[N];
bool cut[N], vis[N << 1];
vector<int> dcc[N];
struct Edge { int to, nxt, id; } edges[M << 2];
inline void add(int type, int from, int to, int eid) {
edges[++tot] = (Edge){to, head[type][from], eid}, head[type][from] = tot;
}
void tarjan(int x) {
dfn[x] = low[x] = ++dfsc;
sta[++top] = x;
if (x == root && head[0][x] == 0)
return dcc[++dccCnt].push_back(x);
int son = 0;
for (int i = head[0][x]; i; i = edges[i].nxt) {
int y = edges[i].to;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (dfn[x] <= low[y]) {
son++;
if (x != root || son > 1) cut[x] = 1;
dccCnt++;
while(1){
int z = sta[top--];
dcc[dccCnt].push_back(z);
if (z == y) break;
}
dcc[dccCnt].push_back(x);
}
} else low[x] = min(low[x], dfn[y]);
}
}
void dfs(int x, int fat, int depth) {
vis[x] = 1, fa[x][0] = fat, dep[x] = depth;
for (int i = 1; i <= 15; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = head[1][x]; i; i = edges[i].nxt) {
int y = edges[i].to;
if (vis[y]) continue;
dfs(y, x, depth + 1);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 15; i >= 0; i--)
if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 15; i >= 0; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int main() {
while (1) {
scanf("%d%d", &n, &m);
if (n == 0 && m == 0) break;
tot = dfsc = dccCnt = top = 0;
memset(head, 0, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(cut, 0, sizeof(cut));
for (int x, y, i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
add(0, x, y, i), add(0, y, x, i);
}
for (int i = 1; i <= n; i++) dcc[i].clear();
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(root = i);
int now = dccCnt;
for (int i = 1; i <= n; i++)
if (cut[i]) id[i] = ++now;
for (int i = 1; i <= dccCnt; i++) {
for (int j = 0; j < dcc[i].size(); j++) {
int x = dcc[i][j];
if (cut[x]) add(1, id[x], i, 0), add(1, i, id[x], 0);
bel[x] = i;
}
for (int j = 0; j < dcc[i].size(); j++)
for (int k = head[0][dcc[i][j]]; k; k = edges[k].nxt) if (bel[edges[k].to] == i) eb[edges[k].id] = i;
}
memset(dep, 0, sizeof(dep));
memset(fa, 0, sizeof(fa));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= now; i++) if (!vis[i]) dfs(i, 0, 1);
scanf("%d", &qn);
for (int x, y; qn--;) {
scanf("%d%d", &x, &y);
x = eb[x], y = eb[y];
if (x == y) puts("0");
else printf("%d
", (dep[x] + dep[y] - 2 * dep[lca(x, y)]) / 2);
}
}
return 0;
}