做法:
利用tarjan算法求出每一个节点出现时对应的时间戳dfn。
对于每一个桥,恰有一个节点与其对应。
isb[i]标记i之前的边是不是桥。
当连接两点的时候,求出这两个点到根节点的路径上的边,把这些边的isb设置成0;
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #define MAXN 500001 using namespace std; struct list { int u; int v; int next; }node[MAXN]; int head[MAXN],vis[MAXN]; int isb[MAXN]; int nums; int fa[MAXN]; int n,m,cnt; int dfn[MAXN],low[MAXN],index; void init() { nums=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++)fa[i]=i; cnt=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(isb,0,sizeof(isb)); index=0; } void add(int x,int y) { node[nums].u=x; node[nums].v=y; node[nums].next=head[x]; head[x]=nums++; } void tarjan(int u) { dfn[u]=low[u]=++index; for(int i=head[u];i!=-1;i=node[i].next) { if(vis[i])continue; vis[i]=vis[i^1]=1; int v=node[i].v; if(!dfn[v]) { fa[v]=u; tarjan(v); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) { cnt++; isb[v]=1; } } else { low[u]=min(low[u],dfn[v]); } } } void LCA(int x,int y) { while(x!=y) { if(isb[x])cnt--,isb[x]=0; if(isb[y])cnt--,isb[y]=0; x=fa[x]; y=fa[y]; } } int main() { int x,y; int cas=0; while(~scanf("%d%d",&n,&m)&&(n||m)) { cas++; init(); while(m--) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } tarjan(1); printf("Case %d:\n",cas); scanf("%d",&m); while(m--) { scanf("%d%d",&x,&y); LCA(x,y); cout<<cnt<<endl; } cout<<endl; } }