#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
using namespace std;
#define maxN 100002
#define maxM 400004
#define MIN(a, b) ((a)<(b)?(a):(b))
int n, m, k;
struct node{
    int to, next;
}path[maxM];
int npath, number;
int first[maxN], father[maxN], deep[maxN], deep2[maxN], ancestor[maxN], look[maxN];
bool visited[maxN];

set<int> obrige;
set<int> brige;
set<int>::iterator it;
void dfs1(int u, int f, int d)
{
    int v, p, cnt=0;
    visited[u]=true;
    deep[u]=ancestor[u]=d;
    for(p=first[u]; p!=-1; p=path[p].next){
        v=path[p].to;
        if(v==f&&cnt==0) {cnt++;continue;}
        if(visited[v]) ancestor[u]=MIN(ancestor[u], deep[v]);
        else{
            dfs1(v, u, d+1);
            ancestor[u]=MIN(ancestor[u], ancestor[v]);
            if(ancestor[v]>deep[u]) obrige.insert(u + v*100001);
        }
    }
}
void dfs2(int u, int id, int f, int d){
    int v, p;
    visited[u]=true;
    father[id]=f;
    deep2[id]=d;
    look[u]=id;
    for(p=first[u]; p!=-1; p=path[p].next){
        v=path[p].to;
        if(visited[v]) continue;
        it=obrige.find(u + v*100001);
        if(it!=obrige.end()){
            number++;
            brige.insert(id + number*100001);
            dfs2(v, number, id, d+1);
        }
        else{
            dfs2(v, id, f, d);
        }
    }
}
void addedge(int u, int v)
{
    int tmp;
    u=look[u]; v=look[v];
    while(u!=v){
        if(deep2[u]<deep2[v]) {tmp=u; u=v; v=tmp;}
        it = brige.find(father[u] + u*100001);
        if(it!=brige.end()) brige.erase(it);
        u=father[u];
    }
}
int main()
{
    int tc=1, i, a, b;
//    freopen("1.txt", "r", stdin);
    while(scanf("%d %d", &n, &m)==2){
        if(n==0) break;
        printf("Case %d:\n", tc++);
        brige.clear(); obrige.clear();
        npath=0; memset(visited, false, sizeof(visited)); memset(first, -1, sizeof(first));
        for(i=0; i<m; i++){
            scanf("%d %d", &a, &b);
            path[npath].to=b;
            path[npath].next=first[a];
            first[a]=npath++;

            path[npath].to=a;
            path[npath].next=first[b];
            first[b]=npath++;
        }
        dfs1(1, 1, 1);
        memset(visited, false, sizeof(visited));
        number =1;
        dfs2(1, 1, 1, 1);
        scanf("%d", &k);
        for(i=0; i<k; i++){
            scanf("%d %d", &a, &b);
            addedge(a, b);
            printf("%d\n", brige.size());
        }
        printf("\n");
    }
    return 0;
}

• Re:为什么我缩图了跑了4700ms??? (17) zj_ja 2011-05-14 18:41:55