poj 3694 Network側ダブル接続+LCA

テーマリンク：http://poj.org/problem?id=3694
n個の点、m条の辺、連図をあげます。そしてQ回の操作があります。毎回一つの辺（A、B）を入れて、辺に参加した後、現在どれぐらいの橋があるかを聞きます。出力橋の個数。
問題の構想を解く：まずもとの連通図の辺の双連通を1本の木に縮めて、Q回の操作の過程の中で木に対してLCA操作を行います。コードを具体的に見る：
ネットを見ても縮まない方法があります。
考え方は、http://www.cnblogs.com/kuangbin/p/3184884.html

#include "stdio.h"   //poj 3177        + LCA(      )
#include "string.h"
#include "vector"
#include "queue"
using namespace std;

#define N 100100
#define M 400200

struct node
{
    int x,y;
    bool visit;
    int next;
} edge[2*M];
int idx,head[N];

void Init()
{
    idx = 0;
    memset(head,-1,sizeof(head));
}

void Add(int x,int y)
{
    edge[idx].x = x;
    edge[idx].y = y;
    edge[idx].visit = false;
    edge[idx].next = head[x];
    head[x] = idx++;
}

int time;
int low[N],dfn[N];
inline int MIN(int a,int b)
{
    return a<b?a:b;
}

int st[M],num;  //       
int stackk[2*M],top;  //   (        ，   )

int n,m;
int countt; //           
int belong[N];

void lian_tong(int x)
{
    int t;
    countt++;
    while(1)
    {
        t = stackk[top];
        top--;
        belong[t] = countt;
        if(t==x) break;
    }
}

void DFS(int x)
{
    int i,y;
    stackk[++top] = x;
    low[x] = dfn[x] = ++time;
    for(i=head[x]; i!=-1; i=edge[i].next)
    {
        y = edge[i].y;
        if(edge[i].visit) continue;
        edge[i].visit = edge[i^1].visit = true;
        if(!dfn[y])
        {
            DFS(y);
            low[x] = MIN(low[x],low[y]);
            if(low[y]>dfn[x])
                st[num++] = i;  //   （             ）
        }
        else
            low[x] = MIN(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
        lian_tong(x); //          
}

int ans;
bool mark[N];
int deep[N];
int father[N];
vector<int> vec[N];  //  

void LCA_bfs(int root)
{
    int i,x,y;
    memset(deep,-1,sizeof(deep));
    deep[root] = 0;
    mark[root] = false;
    father[root] = -1;
    queue<int> q;
    q.push(root);
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(i=0; i<(int)vec[x].size(); ++i)
        {
            y = vec[x][i];
            if(deep[y]!=-1) continue;
            deep[y] = deep[x]+1;
            mark[y] = true;
            father[y] = x;
            q.push(y);
        }
    }
}

void swap(int &x,int &y)
{
    int t = x;
    x = y;
    y = t;
}

void LCA(int x,int y)
{
    if(deep[x] > deep[y]) swap(x,y);
    while(deep[x]<deep[y])
    {
        if(mark[y])
        {
            ans--;
            mark[y] = false;
        }
        y = father[y];
    }
    while(x!=y)
    {
        if(mark[x])
        {
            ans--;
            mark[x] = false;
        }
        if(mark[y])
        {
            ans--;
            mark[y] = false;
        }
        x = father[x];
        y = father[y];
    }
}

void Solve()
{
    int i;
    int x,y;
    countt = 0;  //           
    num = 0;  //      
    top = 0; // 
    time = 0;
    memset(dfn,0,sizeof(dfn));
    DFS(1);
    for(i=1; i<=countt; ++i) vec[i].clear();
    for(i=0; i<num; ++i)  //   
    {
        x = edge[st[i]].x;
        y = edge[st[i]].y;
        x = belong[x];
        y = belong[y];
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    LCA_bfs(1);
    ans = countt - 1;
    int Q;
    int u,v;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d %d",&u,&v);
        LCA(belong[u],belong[v]);
        printf("%d
",ans);
    }
    printf("
");
}

int main()
{
    int i;
    int Case=0;
    int x,y;
    while(scanf("%d %d",&n,&m),n+m)
    {
        Init();
        Case++;
        for(i=0; i<m; ++i)
        {
            scanf("%d %d",&x,&y);
            Add(x,y);
            Add(y,x);
        }
        printf("Case %d:
",Case);
        Solve();
    }
    return 0;
}