传送门：Network
题意：给你一个连通图，然后再给你n个询问，每个询问给一个点u,v表示加上u,v之后又多少个桥。
分析：方法(1219ms)：用并查集缩点，把不是桥的点缩成一个点，然后全图都是桥，每次加边的两个点如果是缩后的同个点，必定不是桥，否则是桥，再把它们到达lca之间的点缩成一点。
方法2（A巨思路360ms）：先一次tarjan缩点，重新建图得到一颗树，每次加边，两个端点到它们的lca之间的边都不再是桥，所以每一次我们都可以通过暴力求出lca，然后统计出少了多少条桥，但是暴力统计时，会遇到某些边在之前就不是桥的情况，我们用并查集来跳过这些边（每一次加边就把lca路径上的点都合并到一个集合里去，这里根用最上面的点，到时如果遇到这种点，直接可以跳到它们的根上去）
方法1：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N<<];
int n,step,top,tot,num;
int head[N],dfn[N],low[N],Stack[N];
bool instack[N],vis[N<<];
int pre[N],fa[N];
void init()
{
tot=;step=;top=;num=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(pre,);FILL(vis,);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int merge(int x,int y)
{
int a=find(x);
int b=find(y);
if(a!=b)
{
fa[b]=a;return ;
}
return ;
}
void tarjan(int u)
{
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(vis[i])continue;
vis[i]=vis[i^]=;
if(!dfn[v])
{
tarjan(v);
pre[v]=u;
if(low[u]>low[v])low[u]=low[v];
//桥：一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS[u]<Low[v]
if(low[v]>dfn[u])
{
num++;
}
else merge(u,v);
}
else if(low[u]>dfn[v])
{
low[u]=dfn[v];
}
}
instack[u]=false;
top--;
}
void lca(int a,int b)
{
while(a!=b)
{
while(dfn[a]>=dfn[b]&&a!=b)
{
if(merge(a,pre[a]))num--;
a=pre[a];
}
while(dfn[a]<=dfn[b]&&a!=b)
{
if(merge(b,pre[b]))num--;
b=pre[b];
}
}
}
void solve()
{
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
int q,u,v;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
lca(u,v);
printf("%d\n",num);
}
puts("");
}
int main()
{
int m,u,v,cas=;
while(scanf("%d%d",&n,&m)&&(n||m))
{
init();
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
printf("Case %d:\n",cas++);
solve();
}
}
方法2：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e1[N<<],e2[N<<];
int n,scc,step,top,tot1,tot2;
int head1[N],head2[N],dfn[N],low[N],belong[N],Stack[N];
int deep[N],fa[N],pre[N];
bool instack[N],vis[N<<];
void init()
{
tot1=;tot2=;step=;scc=;top=;
FILL(head1,-);FILL(head2,-);
FILL(low,);FILL(dfn,);
FILL(instack,false);FILL(vis,);
}
void addedge1(int u,int v)
{
e1[tot1]=edge(v,head1[u]);
head1[u]=tot1++;
}
void addedge2(int u,int v)
{
e2[tot2]=edge(v,head2[u]);
head2[u]=tot2++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head1[u];~i;i=e1[i].next)
{
v=e1[i].v;
if(vis[i])continue;
vis[i]=vis[i^]=;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
}while(v!=u);
}
}
void dfs_dep(int u,int f,int dep)
{
pre[u]=f;deep[u]=dep;
for(int i=head2[u];~i;i=e2[i].next)
{
int v=e2[i].v;
if(v==f)continue;
dfs_dep(v,u,dep+);
}
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int LCA(int u,int v)
{
while(u!=v)
{
if(deep[u]>=deep[v]&&u!=v)
{
u=pre[u];
}
if(deep[v]>=deep[u]&&u!=v)
{
v=pre[v];
}
u=find(u);
v=find(v);
}
return u;
}
void solve()
{
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int u=;u<=n;u++)
{
for(int i=head1[u];~i;i=e1[i].next)
{
int v=e1[i].v;
if(belong[v]!=belong[u])
{
addedge2(belong[u],belong[v]);
}
}
}
dfs_dep(,,);
for(int i=;i<=scc;i++)fa[i]=i;
int ans=scc-,q,u,v;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
int a=find(belong[u]);
int b=find(belong[v]);
int lca=LCA(a,b);
while(a!=b)
{
if(deep[a]>=deep[b]&&a!=b)
{
ans--;
fa[a]=lca;
a=pre[a];
}
if(deep[b]>=deep[a]&&a!=b)
{
ans--;
fa[b]=lca;
b=pre[b];
}
a=find(a);
b=find(b);
}
printf("%d\n",ans);
}
}
int main()
{
int m,u,v,cas=;
while(scanf("%d%d",&n,&m)&&(n||m))
{
init();
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge1(u,v);
addedge1(v,u);
}
printf("Case %d:\n",cas++);
solve();
}
}