POJ 3694 雙連通縮點+LCA+并查集

題意：

給定n個點m條邊的無向圖

Q個詢問：

問加上這條邊後圖中還有多少橋。

注意詢問不是獨立的（加了邊在後面都有效）

思路：

先縮點得到縮點樹，加上一條邊後[u, LCA(u,v), v] 成環，則删掉這裡的點，并把集合向上合并

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <queue>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define inf 107374182
#define ll int

using namespace std;
#define N 100100
//N為點
#define M 200100

struct Edge{  
	int from, to, nex;  
	bool cut;  
}edge[M*2];  
int head[N], edgenum;  
void addedge(int u, int v){  
	Edge E={u,v,head[u],false};  
	edge[ edgenum ] = E;  
	head[u] = edgenum++;  
}  
int n, m;  
int dfn[N], low[N], tarjan_time, tar, Stack[N*5], top;  
int Belong[N];  
bool iscut[N];  
void tarjan(int u, int fa){  
	dfn[u] = low[u] = ++tarjan_time;  
	Stack[++top] = u;  
	int child = 0, flag = 1;  

	for(int i = head[u]; ~i; i = edge[i].nex)  
	{  
		int v = edge[i].to;  
		if(flag && v==fa){flag = 0; continue;}  
		if(!dfn[v])  
		{  
			child++;  
			tarjan(v, u);  
			low[u] = min(low[u], low[v]);  
			if(low[v] >= dfn[u])  
			{  
				iscut[u] = true;  
				if(low[v]>dfn[u])  
					edge[i].cut = edge[i^1].cut = true;  
			}  
		}  
		else low[u] = min(low[u], dfn[v]);  
	}  
	if(child == 1 && fa<0)iscut[u] = false;  
	if(low[u] == dfn[u])  
	{  
		tar++;
		do  
		{  
			Belong[ Stack[top] ] = tar; 
		}while(Stack[top--] != u);  
	}  
}  


void init(){  
	memset(dfn, 0, sizeof(dfn));  
	memset(low, 0, sizeof(low));  
	memset(iscut, 0, sizeof(iscut));  
	memset(Belong, -1, sizeof(Belong));  
	tarjan_time = 0;  
	top = 0;  
	tar = 0;  
	tarjan(1,1);
}  

vector<int>G[N];

const int MAXN = 101000;
int rmq[2*MAXN];//rmq數組，就是歐拉序列對應的深度序列
vector<int>son[N];
int Father[N];
struct ST
{
	int mm[2*MAXN];
	int dp[2*MAXN][20];//最小值對應的下标
	void init(int n)
	{
		mm[0] = -1;
		for(int i = 1;i <= n;i++)
		{
			mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
			dp[i][0] = i;
		}
		for(int j = 1; j <= mm[n];j++)
			for(int i = 1; i + (1<<j) - 1 <= n; i++)
				dp[i][j] = rmq[dp[i][j-1]] < rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
	}
	int query(int a,int b)//查詢[a,b]之間最小值的下标
	{
		if(a > b)swap(a,b);
		int k = mm[b-a+1];
		return rmq[dp[a][k]] <= rmq[dp[b-(1<<k)+1][k]]?dp[a][k]:dp[b-(1<<k)+1][k];
	}
};

int F[MAXN*2];//歐拉序列，就是dfs周遊的順序，長度為2*n-1,下标從1開始
int P[MAXN];//P[i]表示點i在F中第一次出現的位置
int cnt;
ST st;
int deep[N];
void dfs(int u,int pre,int dep)
{
	F[++cnt] = u;
	rmq[cnt] = dep;
	P[u] = cnt;
	for(int i = 0;i <G[u].size(); i++)
	{
		int v = G[u][i];
		if(v == pre)continue;
		dfs(v,u,dep+1);
		F[++cnt] = u;
		rmq[cnt] = dep;
		son[u].push_back(v);
		Father[v] = u;
		deep[v] = deep[u]+1;
	}
}
void LCA_init(int root,int node_num)//查詢LCA前的初始化
{
	cnt = 0;
	dfs(root,root,0);
	st.init(2*node_num-1);
}
int query_lca(int u,int v)//查詢u,v的lca編号
{
	return F[st.query(P[u],P[v])];
}
int f[N];
int find(int x){return x==f[x]?x:f[x] = find(f[x]);}
void Union(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx==fy)return ;
	if(deep[fx]<deep[fy])swap(fx,fy);
	f[fx] = fy;
}
int main(){
	int i, j, u, v, Cas = 1, Q;
	while(scanf("%d %d",&n,&m),n+m){
		printf("Case %d:\n", Cas++);
		for(i=0;i<=n;i++)f[i]=i;
		memset(head, -1, sizeof(head)), edgenum = 0;
		while(m--)
		{
			scanf("%d %d",&u,&v);
			addedge(u,v); addedge(v,u);
		}
		init();
		for(i=0;i<=tar;i++)G[i].clear();
		for(i=0;i<edgenum;i++){
			u = Belong[edge[i].from], v = Belong[edge[i].to];
			if(u!=v)G[u].push_back(v);
		}
		for(i = 0;i<=tar;i++)son[i].clear();
		Father[1] = 1;
		deep[1] = 0;
		LCA_init(1,tar);
		int now = tar-1;
		scanf("%d",&Q);
		while(Q--)
		{
			scanf("%d %d",&u,&v);if(now==0){puts("0");continue;}
			u = Belong[u], v =Belong[v];
			int fa = query_lca(u, v); 
			fa = find(fa);
			u = find(u);
			v = find(v);
			while(u!=fa){
				now--;
				f[u] = fa;
				u = Father[u];
				u = find(u);
			}
			while(v!=fa){
				now--;
				f[v] = fa;
				v = Father[v];
				v = find(v);
			}
			printf("%d\n", now);
		}
	}
	return 0;
}