POJ 3694 network 无向图求桥 手记栈版tarjan

POJ 3694 network 无向图求桥 手写栈版tarjan

这题以前做过

大意就是给出一个无向图，然后每次询问加一条边，然后输出当前图中剩余的桥的个数

大概做法就是先tarjan把桥都弄出来，然后每次加边就裸求LCA。

不过很蛋疼的事情就是在HDU上会爆栈，这很贱，所以有必要弄个手写栈版得tarjan

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 111111
#define MAXM 555555
#define INF 1000000011
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define eps 1e-7
using namespace std;
struct Edge
{
    int v, next;
}edge[MAXM];
int head[MAXN], e, n, m;
int dfn[MAXN], low[MAXN], fa[MAXN];
int index, tmpdfn, vis[MAXN];
int cnt, bridge[MAXN];
int st[MAXN];
void init()
{
    e = index = cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(bridge, 0, sizeof(bridge));
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; i++) fa[i] = i;
}
void add(int u, int v)
{
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e++;
}
void tarjan()
{
    int top = 0;
    st[++top] = 1;
    while(top)
    {
        int u = st[top];
        if(!vis[u])
        {
            dfn[u] = low[u] = ++index;
            vis[u] = 1;
        }
        int i;
        for(i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(!vis[v])
            {
                fa[v] = u;
                break;
            }
            else if(vis[v] == 1 && v != fa[u]) low[u] = min(low[u], dfn[v]);
        }
        if(i == -1 && top > 1)
        {
            low[st[top - 1]] = min(low[u], low[st[top - 1]]);
            if(low[u] > dfn[st[top - 1]])
            {
                bridge[u] = 1;
                cnt++;
            }
        }
        if(i == -1)
        {
            vis[u] = 2;
            top--;
        }
        else st[++top] = edge[i].v;
    }
}
void LCA(int u, int v)
{
    while(dfn[u] > dfn[v])
    {
        if(bridge[u]) cnt--, bridge[u] = 0;
        u = fa[u];
    }
    while(dfn[v] > dfn[u])
    {
        if(bridge[v]) cnt--, bridge[v] = 0;
        v = fa[v];
    }
    while(u != v)
    {
        if(bridge[u]) cnt--, bridge[u] = 0;
        u = fa[u];
        if(bridge[v]) cnt--, bridge[v] = 0;
        v = fa[v];
    }
}
void gao()
{
    int q;
    scanf("%d", &q);
    while(q--)
    {
       int x, y;
       scanf("%d%d", &x, &y);
       LCA(x, y);
       printf("%d\n", cnt);
    }
    printf("\n");
}
int main()
{
    int cas = 0;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(!n && !m) break;
        init();
        int x, y;
        while(m--)
        {
            scanf("%d%d", &x, &y);
            add(x, y);
            add(y, x);
        }
        tarjan();
        printf("Case %d:\n", ++cas);
        gao();
    }
    return 0;
}