2014
11-30

# Traffic Real Time Query System

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 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

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

5 6
1 2
1 3
2 3
3 4
4 5
3 5
2
2 3
2 4
0 0

0
1

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back

const int maxn = 10000 + 10;    // 点的个数
const int maxm = 100000 + 10;   // 边的个数

struct Edge {
int u, to, next, vis, id;
}edge[maxm<<1];

int head[maxn<<1], dfn[maxn<<1], low[maxn], st[maxm], iscut[maxn], subnet[maxn], bian[maxm];
int E, time, top, btot;
vector<int> belo[maxn]; //点属于哪个块

//加边
void newedge(int u, int to) {
edge[E].u = u;
edge[E].to = to;
edge[E].vis = 0;
}

void init(int n) {
for(int i = 0;i <= n; i++) {
dfn[i] = iscut[i] = subnet[i] = 0;
belo[i].clear();
}
E = time = top = btot = 0;
}

void dfs(int u) {
dfn[u] = low[u] = ++time;
for(int i = head[u];i != -1;i = edge[i].next) {
if(edge[i].vis) continue;
edge[i].vis = edge[i^1].vis = 1;
int to = edge[i].to;
st[++top] = i;
if(!dfn[to]) {
dfs(to);
low[u] = min(low[u], low[to]);
// 缩点成块
if(low[to] >= dfn[u]) {
subnet[u]++;
iscut[u] = 1;
btot++;
do {
int now = st[top--];
belo[edge[now].u].pb(btot);
belo[edge[now].to].pb(btot);
bian[edge[now].id] = btot;  //　记录某边属于哪个块
to = edge[now].u;
}while(to != u);
}
}
else
low[u] = min(low[u], low[to]);
}
}

int B[maxn<<2], F[maxn<<2], d[maxn<<2][20], pos[maxn<<2], tot, dep[maxn<<1];
bool treecut[maxn<<1];  // 缩点成树后每个点是否为割点

// RMQ 求lca
void RMQ_init(int n) {
for(int i = 1;i <= n; i++)  d[i][0] = B[i];
for(int j = 1;(1<<j) <= n; j++)
for(int i = 1;i + j - 1 <= n; i++)
d[i][j] = min(d[i][j-1], d[i + (1<<(j-1))][j-1]);
}

int RMQ(int L, int R) {
int k = 0;
while((1<<(k+1)) <= R-L+1)  k++;
return min(d[L][k], d[R-(1<<k)+1][k] );
}

int lca(int a, int b) {
if(pos[a] > pos[b])   swap(a, b);
int ans = RMQ(pos[a], pos[b]);
return F[ans];
}

// 搜树来构造RMQ LCA
void DFS(int u) {
dfn[u] = ++time;
B[++tot] = dfn[u];
F[time] = u;
pos[u] = tot;
for(int i = head[u];i != -1;i = edge[i].next){
int to = edge[i].to;
if(!dfn[to]) {
if(treecut[u])
dep[to] = dep[u] + 1;
else
dep[to] = dep[u];
DFS(to);
B[++tot] = dfn[u];
}
}
}

void solve(int n) {
for(int i = 0;i <= n; i++)  {
dfn[i] = 0;
}
time = tot = 0;
for(int i = 1;i <= n; i++) if(!dfn[i]) {
dep[i] = 0;
DFS(i);
}
RMQ_init(tot);
int m, u, to;
scanf("%d", &m);
while(m--) {
scanf("%d%d", &u, &to);
u = bian[u]; to = bian[to];
if(u < 0 || to < 0) {
printf("0\n"); continue;
}
int LCA = lca(u, to);
if(u == LCA)
printf("%d\n", dep[to] - dep[u] - treecut[u]);
else if(to == LCA)
printf("%d\n", dep[u] - dep[to] - treecut[to]);
else
printf("%d\n", dep[u] + dep[to] - 2*dep[LCA] - treecut[LCA]);
}
}

int main() {
int n, m, u, to;
while(scanf("%d%d", &n, &m) != -1 && n){
init(n);
for(int i = 1;i <= m; i++) {
scanf("%d%d", &u, &to);
edge[E].id = i;
newedge(u, to);
edge[E].id = i;
newedge(to, u);
}

for(int i = 1;i <= n;i ++) if(!dfn[i]) {
dfs(i);
subnet[i]--;
if(subnet[i] <= 0)  iscut[i] = 0;
}
int ditot = btot;   // 树的总节点数
for(int i = 1;i <= btot; i++) treecut[i] = 0;
for(int i = 1;i <= btot+n; i++)  head[i] = -1;
E = 0;
for(int i = 1;i <= n; i++) if(iscut[i]) {
sort(belo[i].begin(), belo[i].end());
ditot++;
treecut[ditot] = 1;
newedge(belo[i][0], ditot);
newedge(ditot, belo[i][0]);
// 割点与相邻块连边
for(int j = 1;j < belo[i].size(); j++) if(belo[i][j] != belo[i][j-1]) {
newedge(belo[i][j], ditot);
newedge(ditot, belo[i][j]);
}
}
solve(ditot);
}
return 0;
}


, ,
1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。