连通专题：双连通+加边+求桥的数量

题目链接：http://poj.org/problem?id=3694
题目大意：在无向图中 在线加边询问桥的数量。
思路：刚开始准备对每次加边，直接求桥。10^8复杂度。然后T了。
看了题解。换了种思路：缩点成树。树上加边。每次把这两点到LCA路径上的点进行缩点。求LCA用倍增。发现维护不了。

又去研究代码：发现根本不要显式缩点。直接并查集维护，这些点是否属于同一双连通分量。每次加边。在dfs树上用深度，回溯到LCA。先回溯到同一深度。再同时回溯。如果u与fa[u]不在同一并查集。那么说明：u到fa[u]为桥，要进行合并并查集。并查集优化后时间复杂度比刚才的要小。在Tarjan()时可以直接求出每个点的并查集。

Tarjan()求并查集的时候有个错误的思路：

if(low[v]<=dfn[u])//不是桥，同属于一个强连通分量
{
	 //p[u]=v;//直接把p[u]连接在v上 错误
  	 L(u ,v); //把u， v的连接同一集合 正确(保证一个连通分量的p[x]相等)
}
else //桥
{
 	  ans++;
}

当时这个错误很多样例都可以过。也一直觉得自己的思路没有问题。
把p[u]连接到v。不就是把u， v的连接同一集合了吗？为什么会WA。
一直在冥思苦想。终于想出来个样例。

4 5
1 3
2 4
3 2
4 1
1 2
2
3 4

现在1, 3根本不属于一个并查集。但实际上是一个双连通分量。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct Node
{
    int to;
    int next; //起点相同的上一条边下标
    bool cut; //边是否为桥
}edge[maxn*4];//双向边开2倍。

int cut, ans=0;//边数

int head[maxn];//点i的最后一条边

int p[maxn];   //并查集初始化:p[i]=i;
int dfn[maxn]; //dfn树的深度
int fa[maxn];  //父节点
int low[maxn];
int N;         //连通分量数

void addEdge(int u, int v)
{
    edge[cut].to=v;
    edge[cut].next=head[u];
    edge[cut].cut=0;
    head[u]=cut++;
}

int F(int x)
{
    return p[x]==x?x:p[x]=F(p[x]);
}

int L(int x, int y)
{
    x=F(x);
    y=F(y);
    if(x!=y)
    {
        p[x]=y;
        return 1;
    }
    return 0;
}

void Tarjan(int u, int e, int tot)
{
    low[u]=dfn[u]=tot;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(i==(e^1))//这里只会去重该边的反边,不会去它的重边
        {
            continue;
        }
        if(dfn[v]==0)
        {
            fa[v]=u;
            Tarjan(v, i, tot+1);
            low[u]=min(low[u], low[v]);

            if(low[v]<=dfn[u])
            {
                L(u ,v);
            }
            else                //桥
            {
                ans++;          //桥的数量
            }
        }
        else if(dfn[v]<dfn[u])
        {
            low[u]=min(low[u], dfn[v]);
        }
    }
}

int LCA(int u, int v)  //回溯到LCA
{
    while(dfn[u]>dfn[v])
    {
        if(L(u, fa[u]))
        {
            ans--;
        }
        u=fa[u];
    }
    while(dfn[u]<dfn[v])
    {
        if(L(v, fa[v]))
        {
            ans--;
        }
        v=fa[v];
    }
    while(u!=v)
    {
        if(L(v, fa[v]))
        {
            ans--;
        }
        v=fa[v];

        if(L(u, fa[u]))
        {
            ans--;
        }
        u=fa[u];
    }
}

int main()
{
    int n,m,a,b,t=1;
    while(scanf("%d%d",&n,&m),m*n)
    {
        memset(head, -1, sizeof(head));
        memset(fa, 0, sizeof(fa));
        cut=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a, b);
            addEdge(b, a);
        }

        memset(dfn, 0, sizeof(dfn));
        N=0;
        ans=0;
        for(int i=1;i<=n;i++)
        {
            p[i]=i;
        }
        for(int i=1;i<=n;i++)
        {
            if(dfn[i]==0)
            {
                Tarjan(i, -1, 1);
            }
        }
        int q;
        scanf("%d",&q);
        printf("Case %d:\n",t++);
        while(q--)
        {
            scanf("%d %d",&a,&b);
            if(F(a)!=F(b))
            {
                LCA(a, b);
            }
            cout<<ans<<endl;
        }
        cout<<endl;
    }

    return 0;
}