「POJ3694」Network

题意：给定一张 $N$ 个点 $M$ 条边的无向连通图，然后执行 $Q$ 次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量。

求桥的数量，先用 $Tarjan$ 算法，求出所有的边双连通分量(即 $e-DCC$)，然后缩点得到一棵树，树上的边的数量就是桥的数量。

对于每一个添加的边 $(x,y)$，如果 $x$ 和 $y$ 属于同一个 $e-DCC$，那么对答案没有任何影响，答案不变；

如果不属于同一个 $e-DCC$，那么 $c[x]$ 到 $c[y]$ 之间的路径上每条边都不是桥($c[x]$ 代表点 $x$ 所属 $e-DCC$ 的编号)。我们求出 $c[x]$ 和 $c[y]$ 的 $LCA$ 为 $p$，从 $c[x]$ 和 $c[y]$ 不断往上走到 $p$，经过的边都不是桥，如果有 $r$ 条边得到标记，答案减去 $r$。

为了让标记的速度更快，可以用并查集优化，当每条边不在是桥后，就把该点合并到父节点上，以后每一步直接用并查集的 $getfa$ 操作跳到上一个节点即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,t,k;
int head1[201010],cnt=1;//缩点前
int head2[201010],tot=1;//缩点后
int dfn[101010],low[101010];//tarjan
int bridge[201010],dep[101010];//桥边，lca所用的深度
int f[101010][21],c[101010],num;//lca所用f，点所属e-DCC编号,e-DCC数量
int fa[101010],ans,Index;//并查集,答案,dfn和low初始
struct node
{
	int next;
	int to;
}e1[801010],e2[801010];//缩点前缩点后
void add(int from,int to,node e[],int &id,int head[])//建图
{
	e[++id].next=head[from];
	e[id].to=to;
	head[from]=id;
}
void tarjan(int u,int edge)//tarjan求桥
{
	dfn[u]=low[u]=++Index;
	for(int i=head1[u];i;i=e1[i].next)
	{
		int v=e1[i].to;
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				bridge[i]=bridge[i^1]=true;
		}
		else if(i!=(edge^1))
			low[u]=min(low[u],dfn[v]);
	}
}
void dfs1(int u)//dfs1给e-DCC编号
{
	c[u]=num;
	for(int i=head1[u];i;i=e1[i].next)
	{
		int v=e1[i].to;
		if(c[v]||bridge[i])
			continue;
		dfs1(v);
	}
}
void dfs2(int u)//dfs2预处理LCA
{
	for(int i=head2[u];i;i=e2[i].next)
	{
		int v=e2[i].to;
		if(dep[v])
			continue;
		dep[v]=dep[u]+1;
		f[v][0]=u;
		for(int j=1;j<=20;j++)
			f[v][j]=f[f[v][j-1]][j-1];
		dfs2(v);
	}
}
int lca(int x,int y)//求LCA
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
void clear()
{
	k++;
	cnt=tot=1;
	Index=num=ans=0;
	memset(head1,0,sizeof(head1));
	memset(head2,0,sizeof(head2));
	memset(e1,0,sizeof(e1));
	memset(e2,0,sizeof(e2));
	memset(bridge,0,sizeof(bridge));
	memset(f,0,sizeof(f));
	memset(dep,0,sizeof(dep));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(c,0,sizeof(c));
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF&&n+m)
	{
		clear();
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b,e1,cnt,head1);
			add(b,a,e1,cnt,head1);
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i])
				tarjan(i,0);//tarjan找e-DCC
		for(int i=1;i<=n;i++)
			if(!c[i])
			{
				++num;
				dfs1(i);//编号
			}
		for(int i=2;i<=cnt;i++)
		{
			int a=e1[i^1].to;
			int b=e1[i].to;
			if(c[a]==c[b])
				continue;
			add(c[a],c[b],e2,tot,head2);//缩点建新图
		}
		dep[1]=1;
		dfs2(1);//预处理LCA
		for(int i=1;i<=num;i++)
			fa[i]=i;//并查集初始化
		ans=num-1;//此时答案为桥的数量，即新图中边的数量，由于缩点后新图是一棵树，所以为点数-1
		scanf("%d",&t);
		printf("Case %d:\n",k);
		for(int i=1;i<=t;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(c[a]==c[b])
			{
				printf("%d\n",ans);
				continue;//如果在同一个分量答案不变
			}
			a=c[a];
			b=c[b];
			int p=lca(a,b);//求出lca
			a=getfa(a);
			while(dep[a]>dep[p])
			{
				fa[a]=f[a][0];
				ans--;//向上标记，构成环答案减1
				a=getfa(a);//向上传
			}
			b=getfa(b);
			while(dep[b]>dep[p])
			{
				fa[b]=f[b][0];
				ans--;
				b=getfa(b);//另外一边同理
			}
			printf("%d\n",ans);
		}
		printf("\n");
	}
	return 0;
}