题意：
一个无向图可以有重边，下面q个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上）。
思路：
首先运行一次Tarjan，求出桥和缩点，那么远无向图将缩点为一棵树，树边正好是原来的桥。每次连接两点，看看这两点是不是在同一个缩点内，如果是，那么缩点后的树没任何变化，如果两点属于不同的缩点，那么连接起来，然后找这两个缩点的LCA，因为从点u到LCA再到点v再到点u，将形成环，里面的树边都会变成不是桥。计数的时候注意，有些树边可能之前已经被标记了，这次再经过不能再标记。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;#define N 100010#define M 200010vector<int> ver[N];int head[N],dfn[N],low[N],vis[N],fa[N],dcnt,bcnt;struct edge{ ???int u,v,used,next;}e[2*M];bool isbridge[N];inline void add(int u, int v ,int &k){ ???e[k].v = v; e[k].used = 0; ???e[k].next = head[u]; head[u] = k++;}void LCA(int u,int v){ ???if(dfn[u] < dfn[v]) swap(u,v); ???while(dfn[u] > dfn[v]) ???{ ???????if(isbridge[u]) bcnt--; ???????isbridge[u] = false; ???????u = fa[u]; ???} ???while(u!=v) ???{ ???????if(isbridge[u]) bcnt--; ???????if(isbridge[v]) bcnt--; ???????isbridge[u] = isbridge[v] = false; ???????u = fa[u]; v = fa[v]; ???}}void dfs(int u){ ???vis[u] = 1; dfn[u] = low[u] = ++dcnt; ???for(int k=head[u]; k!=-1; k=e[k].next) ???????if(!e[k].used) ???????{ ???????????e[k].used = e[k^1].used = 1; ???????????int v = e[k].v; ???????????if(!vis[v]) ???????????{ ???????????????fa[v] = u; ???????????????dfs(v); ???????????????low[u] = min(low[u] , low[v]); ???????????????if(dfn[u] < low[v]) ???????????????{ bcnt++; isbridge[v] = true; } ???????????} ???????????else if(vis[v] == 1) low[u] = min(low[u],dfn[v]); ???????} ???vis[u] = 2;}int main(){ ???int n,m,q,cas=0; ???while(cin>>n>>m,n,m) ???{ ???????memset(head,-1,sizeof(head)); ???????int k = 0; ???????for(int i=0; i<m; i++) ???????{ ???????????int u,v; ???????????cin>>u>>v; ???????????add(u,v,k); ???????????add(v,u,k); ???????} ???????memset(isbridge,false,sizeof(isbridge)); ???????memset(vis,0,sizeof(vis)); ???????dcnt = bcnt = 0; ???????fa[1] = 1; ???????dfs(1); ???????printf("Case %d:\n",++cas); ???????cin>>q; ???????while(q--) ???????{ ???????????int u,v; ???????????cin>>u>>v; ???????????LCA(u,v); ???????????cout<<bcnt<<endl; ???????} ???????cout<<endl; ???} ???return 0;}POJ3694 Network【连通分量+LCA】
原文地址：http://www.cnblogs.com/darklights/p/7642660.html