记录编号	586121	评测结果	AAAAAAAAAA
题目名称	[POJ 3694]Network	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2024-01-05 18:05:41	内存使用	9.04 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 3e5+10;
int n,m,q;
struct made{
    int ver,nx;
}e[N<<1];
struct line{
    int x,y;
}li[N];
int hd[N],tot,cnt,top,num;
int dfn[N],low[N],c[N],st[N];
int fa[N],dep[N],belong[N];
bool v[N];
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
int find(int x){
    if(belong[x] == x)return x;
    return belong[x] = find(belong[x]);
}
void tarjan(int x,int in_){
    dfn[x] = low[x] = ++cnt;
    st[++top] = x,v[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(i == (in_^1))continue;
        if(!dfn[y])tarjan(y,i),low[x] = min(low[x],low[y]);
        else if(v[y])low[x] = min(low[x],dfn[y]);
    }
    if(low[x] == dfn[x]){
        num++;int y = 0;
        do{
            y = st[top--];
            v[y] = 0,c[y] = num;
        }while(x != y);
    }
}
void dfs(int x,int ff){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y == ff)continue;
        fa[y] = x;dep[y] = dep[x] + 1;
        dfs(y,x);
    }
}
int work(int x,int y){
    if(x == y)return x;
    if(dep[x] < dep[y])swap(x,y);
    num--;
    return belong[x] = work(find(fa[x]),y);
}
void first(){
    tot = 1;
    num = cnt = top = 0;
    memset(hd,0,sizeof(hd));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(fa,0,sizeof(fa));
    memset(dep,0,sizeof(dep));
    memset(c,0,sizeof(c));
}
int main(){
    freopen("Networks.in","r",stdin);
    freopen("Networks.out","w",stdout);
    int t = 0;
    while(scanf("%d%d",&n,&m) && n && m){
        first();
        for(int i = 1;i <= m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
            li[i].x = x,li[i].y = y;
        }
        tarjan(1,0);
        tot = 1;
        memset(hd,0,sizeof(hd));
        for(int i = 1;i <= m;i++){
            int x = li[i].x,y = li[i].y;
            if(c[x] == c[y])continue;
            add(c[x],c[y]),add(c[y],c[x]);
        }
        dep[1] = 1;
        dfs(1,0);
        for(int i = 1;i <= num;i++)belong[i] = i;
        scanf("%d",&q);
        printf("Case %d:\n",++t);
        for(int i = 1;i <= q;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            work(find(c[x]),find(c[y]));
            printf("%d\n",num-1);
        }
        printf("\n");
    }
    
    return 0;
    
}