题目描述：给你一个无向连通图，然后陆续加一些边。

每加一条边，让你输出当前图的割边有多少条。

解题报告：

开始时先统计所有割边的个数（tarjan），然后每加一条边，只会减少割边的个数。

随机取一个根，建立dfs树，确定每一个点的father。

这样，每当连接点a和点b这条边，会就形成一个环，这个环内的边都不是割边。

所以只要找到a，b的lca，把这个路径上的桥标记掉就好了。

代码如下：

#include<iostream>

#include<vector>

using namespace std;

#define N 100001

vector<int> v[N];

int n, m, q, a, b, dfn[N], low[N], num, index, fa[N], level[N];

bool isbridge[N];

void tarjan(int id, int from, int deep)

{

    fa[id] = from, low[id] = dfn[id] = ++index;

    level[id] = deep;

    bool flag = false;

    for(int i = 0; i < v[id].size(); i++)

        if (v[id][i] == from && !flag) flag = true;

        else

        {

            if (!dfn[v[id][i]])

            {

                tarjan(v[id][i], id, deep + 1);

                low[id] = min(low[id], low[v[id][i]]);

                if (low[v[id][i]] > dfn[id])

                {

                    isbridge[v[id][i]] = 1;

                    num++;

                }

            }

            else low[id] = min(low[id], dfn[v[id][i]]);

        }

}

void lca(int u, int v)

{

    if (level[u] < level[v]) swap(u, v);

    while(level[u] > level[v])

    {

        if (isbridge[u])

        {

            num--;

            isbridge[u] = 0;

        }

        u = fa[u];

    }

    while(v != u)

    {

        if (isbridge[u])

            num--, isbridge[u] = 0;

        if (isbridge[v])

            num--, isbridge[v] = 0;

        u = fa[u], v = fa[v];

    }

}

int main()

{

    int ca = 1;

    while(scanf("%d%d", &n, &m) && (n || m))

    {

        for(int i = 1; i <= n; i++) v[i].clear();

        while(m-- && scanf("%d%d", &a, &b))

            v[a].push_back(b), v[b].push_back(a);

        index = 0, num = 0;

        memset(isbridge, 0, sizeof(bool) * (n + 1));

        memset(dfn, 0, sizeof(int) * (n + 1));

        tarjan(1, -1, 0);

        scanf("%d", &q);

        printf("Case %d:\n", ca++);

        while(q-- && scanf("%d%d", &a, &b))

            lca(a, b), printf("%d\n", num);

        putchar('\n');

    }

    return 0;

}