POJ - 3694 Network（無向圖+多重邊+動态加邊+邊雙連通分量+并查集+LCA）

連結：https://cn.vjudge.net/problem/POJ-3694

題意：每加一次邊輸出目前橋的個數。

思路：先将原圖邊雙連通分量求出（順便求出橋（割邊）的個數），并且将邊雙聯通分量縮點。縮點之後重建立圖，肯定是樹或森林，當加一點邊時，如果這條邊的兩個點（假設為u、v）已經在同一個邊雙裡，橋的個數不會變；否則，u、v和LCA（u，v）之間的所有點，都會在同一個邊雙裡，減少的橋就是u->LCA（u，v）和v->LCA（u，v）的邊的個數之和。這裡可以用并查集維護，這樣可以快速的找LCA。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long
using namespace std;
const int N = 1e5+10;
const int M = 5e5+10;
struct node
{
	int to,nxt,id;
}g[M],g1[M];
int head[N],cnt,head1[N],cnt1;
int dfn[N],id,low[N],color[N],cl,sta[N],top;
int f[N],fa[N],deep[N];
int ans;
bool vis[N];
int n,m,q;
void Init()
{
	top=cl=id=cnt=cnt1=ans=0;
	for(int i=1;i<=n;i++)
		head[i]=head1[i]=-1,deep[i]=dfn[i]=vis[i]=0;
}
inline void add(int u,int v,int num)
{
	g[cnt].to=v; g[cnt].nxt=head[u]; g[cnt].id=num; head[u]=cnt++;
	return ;
}
inline void add1(int u,int v)
{
	g1[cnt1].to=v; g1[cnt1].nxt=head1[u]; head1[u]=cnt1++;
	return ;
}
inline void tarjan(int u,int x)
{
	int v;
	dfn[u]=low[u]=++id; sta[++top]=u; vis[u]=1; 
	for(int i=head[u];i!=-1;i=g[i].nxt)
	{
		v=g[i].to;
		//求邊雙時，從父親來的邊不能再走，但此題有多重邊，是以要判斷邊的編号 
		if(g[i].id==x) continue;
		if(!dfn[v])
		{
			tarjan(v,g[i].id);
			low[u]=min(low[u],low[v]);				
		}
		else if(vis[v])
			low[u]=min(low[u],dfn[v]);	
	}
	if(dfn[u]==low[u])
	{
		//邊雙的個數 
		color[u]=++cl;
		while(sta[top]!=u)
		{
			color[sta[top]]=cl; vis[sta[top--]]=0;
		}
		vis[sta[top--]]=0;
	}
	return ;
}
inline void build()
{
	for(int u=1;u<=n;u++)
		for(int i=head[u];i!=-1;i=g[i].nxt)
			if(color[u]!=color[g[i].to]) add1(color[u],color[g[i].to]);
	return ;				
}
inline void dfs(int u)
{
	int v; 
	for(int i=head1[u];i!=-1;i=g1[i].nxt)
	{
		v=g1[i].to;
		if(deep[v]) continue;
		deep[v]=deep[u]+1;
		fa[v]=u;
		dfs(v);
	}
	return ;
}
inline int getf(int x)
{
	return f[x]==x?x:f[x]=getf(f[x]);
}
inline int LCA(int u,int v)
{
	while(u!=v)
	{
		if(deep[u]<deep[v])
			v=fa[v];
		else if(deep[u]>deep[v])
			u=fa[u];
		else u=fa[u],v=fa[v];
		u=getf(u); v=getf(v);
	}
	return u;
}
int main(void)
{
	int u,v,x,lca,tt=0;
	while(~scanf("%d%d",&n,&m)&&(n||m))
	{
		Init();	
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v,i); add(v,u,i);
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i]) tarjan(i,0);
		//tarjan(1,0);
		build();
		
		for(int i=1;i<=cl;i++)
			if(!deep[i]) deep[i]=1,fa[i]=0,dfs(i);
 		//deep[1]=1; fa[1]=0;
		//dfs(1);
		scanf("%d",&q);
		printf("Case %d:\n",++tt);
		
		ans=cl-1;
		for(int i=1;i<=cl;i++) f[i]=i;
		while(q--)
		{
			scanf("%d%d",&u,&v);
			u=color[u]; v=color[v];
			if(u==v)
			{
				printf("%d\n",ans); 
				continue;
			}
			u=getf(u); v=getf(v);
			x=0;
			lca=LCA(u,v);
			while(u!=lca)
			{
				x++;
				f[u]=lca;
				u=fa[u];
				u=getf(u);
			}
			while(v!=lca)
			{
				x++;
				f[v]=lca;
				v=fa[v];
				v=getf(v);
			}
			ans-=x;
			printf("%d\n",ans);
		}
		printf("\n");
	}
	return 0;
}