给你一个存在桥的无向连通图，每次增加一条边，问每次增加边之后还剩多少个桥。

朴素的办法就是每输入一次tarjan求一次桥的个数，肯定会tle；

正确的做发是，首先求出改图的桥的数量，在tarjan的过程中里用并查集把不是桥的边缩为一点，然后得到一棵树，每加入一条边，就肯定会形成一个环，，然后删除环中石桥的边，最后得出总的桥的数量。删除的过程就是检查是否石桥是就有cut--;

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #define maxn 100010 using namespace std; int low[maxn],dfn[maxn],father[maxn],f[maxn]; int index,n,m,q,cut; vector
          
           g[maxn]; void init(int nn) {
    for (int i = 0; i <= n+1; ++i)     {
            g[i].clear();         low[i] = dfn[i] = father[i] = 0;         f[i] = i;     }     index = cut = 0; } int find(int x) {
    if (f[x] != x)     f[x] = find(f[x]); return f[x]; } int Union(int x,int y) {
        x = find(x);     y = find(y); if (x != y)     {
            f[y] = x; return 1;     } else return 0; } void tarjan(int i,int pre) {
    int j,k;     low[i] = dfn[i] = ++index; for (k = 0; k < g[i].size(); ++k)     {
            j = g[i][k]; if (!dfn[j])         {
                tarjan(j,i);             low[i] = min(low[i],low[j]);             father[j] = i;//记录每个节点的父亲，方便后面的环中的查找             if (low[j] > dfn[i])//记录桥数              cut++; else             Union(i,j);//把不是桥的缩为一点         } else if (j != pre)//这里要注意不能是i的父亲，反之low[i] = low[father[i]]了;         {
                low[i] = min(low[i],dfn[j]);         }     } } void lca(int u,int v) {
    //在环中找桥的过程     while (u != v)     {
    while (dfn[u] >= dfn[v] && u != v)         {
    if (Union(u,father[u]))             cut--;             u = father[u];         } while (dfn[v] >= dfn[u] && u != v)         {
    if (Union(v,father[v]))             cut--;             v = father[v];         }     } } int main() {
    //freopen("d.txt","r",stdin);     int i,x,y,cas = 1; while (scanf("%d%d",&n,&m))     {
    if (!n && !m) break;         printf("Case %d:\n",cas++);         init(n); for (i = 0; i < m; ++i)         {
                scanf("%d%d",&x,&y);             g[x].push_back(y);             g[y].push_back(x);         } /*for (i = 1; i <= n; ++i)         {
                 for (int j = 0; j < g[i].size(); ++j)             printf("%d ",g[i][j]);             puts(" ");         }*/         tarjan(1,-1); //printf(">>>%d\n",cut);         cin>>q; while (q--)         {
                cin>>x>>y;             lca(x,y);             printf("%d\n",cut);         }         printf("\n");     } return 0; }