题目链接: http://poj.org/problem?id=3694
题意: 给出一个 n 个节点 m 条边的图, 然后有 q 组形如 x, y 的询问, 在前面的基础上连接边 x, y, 输出当前图中有多少桥 .
思路: http://www.cnblogs.com/scau20110726/archive/2013/05/29/3106073.html
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std; const int MAXN = 1e5 + ; struct node{
int v, next, use;
}edge[MAXN << ]; bool bridge[MAXN];
int low[MAXN], dfn[MAXN], vis[MAXN];
int head[MAXN], pre[MAXN], ip, sol, count; void init(void){
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
memset(bridge, false, sizeof(bridge));
count = sol = ip = ;
} void addedge(int u, int v){
edge[ip].v = v;
edge[ip].use = ;
edge[ip].next = head[u];
head[u] = ip++;
} void tarjan(int u){
vis[u] = ;
dfn[u] = low[u] = count++;
for(int i = head[u]; i != -; i = edge[i].next){
if(!edge[i].use){
edge[i].use = edge[i ^ ].use = ;
int v = edge[i].v;
if(!vis[v]){
pre[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);
if(dfn[u] < low[v]){
sol++;
bridge[v] = true;
}
}else if(vis[v] == ){
low[u] = min(low[u], dfn[v]);
}
}
}
vis[u] = ;
} void LCA(int u, int v){
if(dfn[u] > dfn[v]) swap(u, v);
while(dfn[v] > dfn[u]){//判断一下u,v是否在同一条树枝上
if(bridge[v]) sol--;
bridge[v] = false;
v = pre[v];
}
while(u != v){//找lca
if(bridge[u]) sol--;
if(bridge[v]) sol--;
bridge[u] = bridge[v] = false;
u = pre[u];
v = pre[v];
}
} int main(void){
int n, m, q, x, y, cas = ;
while(~scanf("%d%d", &n, &m)){
if(!n && !m) break;
init();
for(int i = ; i < m; i++){
scanf("%d%d", &x, &y);
addedge(x, y);
addedge(y, x);
}
pre[] = ;
tarjan();
printf("Case %d:\n", cas++);
scanf("%d", &q);
while(q--){
scanf("%d%d", &x, &y);
LCA(x, y);
printf("%d\n", sol);
}
puts("");
}
return ;
}