学步园

//Tarjan求桥 + LCA<br /> //蛋疼题目，确实想不到用LCA这个如此巧妙的方法，主要也就写下求桥，对Tarjan的DFN,LOW值再加深下理解<br /> //重点是对桥的记录，本来想通过用边来记录，后来发现这是无解的，用桥与点对应就可以了<br /> //一开始还想实践下LRJ书里面说的，缩点后形成的树每条边都是桥，后来觉得太难打了..就我这么渣的代码能力，打起来太蛋疼了- -|||<br /> #include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> #include<vector><br /> using namespace std;<br /> const int MAXN = 100005,MAXM = 450005;<br /> int N,M,Q;<br /> int DFN[MAXN],LOW[MAXN],index,num;<br /> int head[MAXN],next[MAXM],V[MAXM],fa[MAXN],edge;<br /> bool bridge[MAXN];<br /> int dep[MAXN],Case;<br /> void addEdge(int u,int v)<br /> {<br /> V[edge] = v;<br /> next[edge] = head[u];<br /> head[u] = edge++;<br /> }<br /> //无向图求桥，对桥而言，都对应着一个后继结点，因此用后继结点记录桥即可<br /> void dfs(int x,int p,int ee,int d)<br /> {<br /> fa[x] = p;<br /> dep[x] = d;<br /> DFN[x] = LOW[x] = ++index;<br /> for(int e = head[x];e != -1;e = next[e])<br /> {<br /> int y = V[e];<br /> if((e ^ 1) == ee) continue;//若为反向边则跳过,只记录父亲是不行的<br /> if(!DFN[y])<br /> {<br /> dfs(y,x,e,d+1);<br /> LOW[x] = min(LOW[x],LOW[y]);<br /> if(LOW[y] > DFN[x])//如果y能到达的深度最小的祖先比x的DFN值还小，证明y没有路径能够到通往x,故y对应着一条桥<br /> {<br /> bridge[y] = 1;<br /> ++num;<br /> }<br /> }<br /> else LOW[x] = min(LOW[x],DFN[y]);//更新x所能通往的深度最小的祖先<br /> }<br /> }<br /> void delBridge(int x)<br /> {<br /> if(bridge[x])<br /> {<br /> bridge[x] = 0;<br /> num--;<br /> }<br /> }<br /> void LCA(int x,int y)//最朴素的LCA求法，记录每个结点的深度，和每个结点的父亲结点<br /> {<br /> if(dep[x] < dep[y]) swap(x,y);<br /> while(dep[x] > dep[y])//先将两个点调节到深度一样的位置<br /> {<br /> delBridge(x);<br /> x = fa[x];<br /> }<br /> while(x != y)//一层层上升，并删除桥<br /> {<br /> delBridge(x);<br /> x = fa[x];<br /> delBridge(y);<br /> y = fa[y];<br /> }<br /> }<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> bool first = 1;<br /> while(scanf("%d%d",&N,&M))<br /> {<br /> if(N == 0 && M == 0) break;<br /> first ? first = 0 : printf("/n");<br /> int x,y;<br /> num = edge = 0;<br /> memset(head,-1,sizeof(head));<br /> memset(bridge,0,sizeof(bridge));<br /> memset(DFN,0,sizeof(DFN));<br /> memset(dep,0,sizeof(dep));<br /> memset(fa,0,sizeof(fa));<br /> while(M--)<br /> {<br /> scanf("%d%d",&x,&y);<br /> addEdge(x,y);<br /> addEdge(y,x);<br /> }<br /> dfs(1,0,-1,1);<br /> printf("Case %d:/n",++Case);<br /> scanf("%d",&Q);<br /> while(Q--)<br /> {<br /> scanf("%d%d",&x,&y);<br /> addEdge(x,y);<br /> addEdge(y,x);<br /> LCA(x,y);<br /> printf("%d/n",num);<br /> }<br /> }<br /> }