题目大意：已知连通图G有N个点m条无向边，有Q次操作，每次操作为增加一条边，问每次操作后图上有几个桥。
如果添加一条边进行Tarjin搜索一次时间复杂度为m*m*q很大，会超时。真的超时，我试过。看了lx学长的题解才
直到有LCA这个东西。LCA算法意思是保存Tarjin搜索树上的父节点和子节点关系，之后对图进行重复操作时不用
再次对图进行搜索，只需要用已经储存的 父节点和子节点关系 进行更新运算即可。这样的时间复杂度为m+q.
附AC代码：
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; struct ad { int to, next, used; }edge[400005]; int head[100005], edge_num, dfn[100005], low[100005], bridge_num, Time, father[100005]; bool isbridge[100005]; void Add(int x, int y)///邻接表储存 { edge[edge_num].to = y; edge[edge_num].next = head[x]; edge[edge_num].used = 0; head[x] = edge_num++; } void Init()///预处理 { memset(head, -1, sizeof(head)); memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(isbridge, false, sizeof(isbridge)); edge_num = Time = bridge_num = 0; } void Tarjin(int u, int fa) { father[u] = fa; low[u] = dfn[u] = ++Time; int i, v; for(i=head[u]; i!=-1; i=edge[i].next) { if(edge[i].used==0) { edge[i].used = edge[i^1].used = 1;///标记反向边 v = edge[i].to; if(!dfn[v]) { Tarjin(v, u); low[u] = min(low[u], low[v]); if(low[v]>dfn[u]) { bridge_num++; isbridge[v] = true; } } else if(v!=fa) low[u] = min(low[u], dfn[v]); } } } void LCA(int u, int v)///利用搜索树的父子节点关系运算 { if(dfn[u]>dfn[v])///保证u是搜索树上靠下的点，依次向上访问.更新.运算 swap(u, v); while(dfn[v]>dfn[u]) { if(isbridge[v])bridge_num--; isbridge[v] = false; v = father[v]; } while(u!=v) { if(isbridge[u])bridge_num--; if(isbridge[v])bridge_num--; isbridge[u] = isbridge[v] = false; u = father[u]; v = father[v]; } } int main() { int n, m, icase = 1; while(scanf("%d %d", &n, &m), n+m) { int a, b; Init(); for(int i=1; i<=m; i++) { scanf("%d %d", &a, &b); Add(a, b); Add(b, a); } Tarjin(1, -1); int Q; scanf("%d", &Q); printf("Case %d: ", icase++); while(Q--) { scanf("%d %d", &a, &b); LCA(a, b); printf("%d ", bridge_num); } } return 0; }