C++14(g++5.4) 解法, 执行用时: 57ms, 内存消耗: 7032K, 提交时间: 2020-08-06 16:52:48

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int head[maxn], to[maxn * 4], Next[maxn * 4];
int f[maxn], ans, pre[maxn];
int dfn[maxn], low[maxn], n, m, tot, num;
bool flag[maxn * 4];
void add(int x, int y)
{
	to[++tot] = y; Next[tot] = head[x]; head[x] = tot;
}
int getf(int x)
{
	return f[x] == x ? x : f[x] = getf(f[x]);
}
bool mer(int x, int y)
{
	int t1 = getf(x);
	int t2 = getf(y);
	if (t1 != t2)	f[t2] = t1;
	else		return false;
	return true;
}
void tarjan(int x, int in_edge, int fa)
{
	dfn[x] = low[x] = ++num; pre[x] = fa;//cout<<x<<" "<<fa<<endl;
	for (int i = head[x]; i; i = Next[i]) {
		int y = to[i];
		if (!dfn[y]) {
			tarjan(y, i, x);
			low[x] = min(low[x], low[y]);
			if (low[y] > dfn[x])
				ans++;
			else
				mer(x, y);
		}
		else	if (i != (in_edge ^ 1))
			low[x] = min(low[x], dfn[y]);
	}
}
void lca(int x, int y)
{
	if (dfn[x] < dfn[y])	swap(x, y);
	while (dfn[x] > dfn[y]) {
		//cout<<x<<" "<<dfn[x]<<" "<<y<<" "<<dfn[y]<<endl;
		if (mer(pre[x], x))	ans--;
		x = getf(pre[x]);
	}
	while (x != y) {
		if (mer(pre[y], y))	ans--;
		y = getf(pre[y]);
	}
}
int main()
{
	int T = 0;
	while (cin >> n >> m) {
		if (n == 0 && m == 0)	break;
		if (T)	printf("\n");
		printf("Case %d:\n", ++T);
		tot = 1; num = 0;
		for (int i = 1; i <= n; i++)
			dfn[i] = low[i] = head[i] = 0, f[i] = i;
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			add(x, y); add(y, x);
		}
		ans = 0;
		for (int i = 1; i <= n; i++)
			if (!dfn[i])	tarjan(i, 0, 0);
		int q; scanf("%d", &q);
		while (q--) {
			int t1, t2; scanf("%d%d", &t1, &t2);
			lca(t1, t2);
			cout << ans << endl;
		}
	}

}

C++(clang++11) 解法, 执行用时: 83ms, 内存消耗: 12004K, 提交时间: 2020-10-26 16:45:00

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int nn=101026;
bool in[nn];
int a,b,t,n,m,q,ans,d[nn],c[nn],fa[nn];
stack<int>st;
vector<int>to[nn],son[nn];
int tarjan(int u,int fa){
	int low,cnt=0;
	in[u]=true,st.push(u);
	low=d[u]=++d[0];
	for(int i=0,v;i<(int)to[u].size();i++)
		if(d[v=to[u][i]]){
			if((v==fa&&cnt++)||v!=fa)low=min(low,d[v]);
		}else low=min(low,tarjan(v,u));
	in[u]=false;
	if(low==d[u]){
		c[u]=++c[0];
		for(;st.top()!=u;st.pop())
			c[st.top()]=c[0];
		st.pop();
	}return low;
}void dfs(int u){
	for(int i=0,v;i<(int)son[u].size();i++)
		if((v=son[u][i])!=fa[u])
			d[v]=d[fa[v]=u]+1,dfs(v);
}int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		if(n==0&&m==0)return 0;
		printf("Case %d:\n",++t);
		while(m--)
			scanf("%d%d",&a,&b),
			to[a].eb(b),to[b].eb(a);
		tarjan(1,0),ans=c[0]-1;
		for(int i=1;i<=n;i++)
			for(int j=0,u=c[i],v;j<(int)to[i].size();j++)
				if(u!=(v=c[to[i][j]]))
					son[u].eb(v),son[v].eb(u);
		for(d[1]=0,dfs(1),scanf("%d",&q);q--;){
			scanf("%d%d",&a,&b),
			a=c[a],b=c[b];
			if(d[a]<d[b])swap(a,b);
			for(;d[a]!=d[b];a=fa[a])
				if(!in[a])in[a]=true,ans--;
			for(;a!=b;a=fa[a],b=fa[b]){
				if(!in[a])in[a]=true,ans--;
				if(!in[b])in[b]=true,ans--;
			}printf("%d\n",ans);
		}putchar('\n');
		for(int i=1;i<=c[0];i++)son[i].clear();
		for(int i=1;i<=n;i++)to[i].clear();
		memset(in,false,sizeof in);
		c[0]=0,memset(d,0,sizeof d);
	}return 0;
}