題意：給一個n個點的無向圖，m條雙向邊，保證沒有重邊和自環，圖連通，有q個詢問，給兩個點，S和T，問從S到T有多少條割邊。
思路：看到這題第一反應就是求雙連通分量，然後縮點，因為在同一個雙連通分量內肯定沒有割邊，然後縮點後原圖就變成了一棵樹，因為保證原圖連通，所以得到的也只有一顆樹，樹中的邊即為原圖中的割邊，於是問題就轉化成求樹中兩點的距離了，用LCA即可解決。先貼一個代碼。
[cpp]
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
using namespace std;
struct edge
{
int to;
int next;
int num;
}e[3][maxn<<2];
int box[3][maxn],cnt[3];
void init()
{
memset(box,-1,sizeof(box));
memset(cnt,0,sizeof(cnt));
}
void add(int from,int to,int num,int t)
{
e[t][cnt[t]].to=to;
e[t][cnt[t]].num=num;
e[t][cnt[t]].next=box[t][from];
box[t][from]=cnt[t]++;
}
int pre[maxn];
int low[maxn];
int bridge[maxn];
int bcnt=0;
int cnt0;
void bridge_search(int now,int fa)
{
int t;
int v,w;
low[now]=pre[now]=++cnt0;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(v==fa)
continue;
if(!pre[v])
{
bridge_search(v,now);
if(low[v]<low[now])
low[now]=low[v];
if(low[v]>pre[now])
{
bridge[e[0][t].num]=1;
}
}
else
{
if(low[now]>pre[v])
low[now]=pre[v];
}
}
}
int Bridge(int n)
{
int i;
cnt0=0;
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
memset(bridge,0,sizeof(bridge));
bcnt=0;
for(i=1;i<=n;i++)
{
if(!pre[i])
{
bridge_search(i,0);
}
}
return bcnt;
}
int vis[maxn];
int dist[maxn];
void Dfs(int now,int num)
{
low[now]=num;
vis[now]=1;
int t,v,nn;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to,nn=e[0][t].num;
if(bridge[nn])
continue;
if(!vis[v])
{
Dfs(v,num);
}
}
}
void solve(int n)//Ëõµã
{
int i,sum=0;
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
{
if(!low[i])
Dfs(i,++sum);
}
for(i=1;i<=n;i++)
{
int t,v;
for(t=box[0][i];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(low[i]!=low[v])
{
add(low[i],low[v],0,1);
add(low[v],low[i],0,1);
}
}
}
}
void dfs(int now,int deep)
{
dist[now]=deep;
vis[now]=1;
int t,v;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(!vis[v])
{
dfs(v,deep+1);
}
}
}
int f[maxn];
void finit(int n)
{
int i;
for(i=0;i<=n;i++)
f[i]=i;
}
int find(int x)
{
if(x==f[x])
return x;
return f[x]=find(f[x]);
}
int ans[maxn];
void lca(int now)
{
f[now]=now;
vis[now]=1;
int t,v,x;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(!vis[v])
{
lca(v);
f[v]=now;
}
}
for(t=box[2][now];t+1;t=e[2][t].next)
{
v=e[2][t].to,x=e[2][t].num;
if(vis[v]==2)
{
int tt=find(v);
ans[x]=dist[now]+dist[v]-2*dist[tt];
}
}
vis[now]=2;
}
int main()
{
//freopen("dd.txt","r",stdin);
int n,m,i,a,b,q;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b,i,0);
add(b,a,i,0);
}
memset(ans,0,sizeof(ans));
Bridge(n);
solve(n);
memset(vis,0,sizeof(vis));
dfs(1,0);
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
if(low[a]!=low[b])
{
add(low[a],low[b],i,2);
add(low[b],low[a],i,2);
}
}
memset(vis,0,sizeof(vis));
lca(1);
for(i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
using namespace std;
struct edge
{
int to;
int next;
int num;
}e[3][maxn<<2];
int box[3][maxn],cnt[3];
void init()
{
memset(box,-1,sizeof(box));
memset(cnt,0,sizeof(cnt));
}
void add(int from,int to,int num,int t)
{
e[t][cnt[t]].to=to;
e[t][cnt[t]].num=num;
e[t][cnt[t]].next=box[t][from];
box[t][from]=cnt[t]++;
}
int pre[maxn];
int low[maxn];
int bridge[maxn];
int bcnt=0;
int cnt0;
void bridge_search(int now,int fa)
{
int t;
int v,w;
low[now]=pre[now]=++cnt0;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(v==fa)
continue;
if(!pre[v])
{
bridge_search(v,now);
if(low[v]<low[now])
low[now]=low[v];
if(low[v]>pre[now])
{
bridge[e[0][t].num]=1;
}
}
else
{
if(low[now]>pre[v])
low[now]=pre[v];
}
}
}
int Bridge(int n)
{
int i;
cnt0=0;
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
memset(bridge,0,sizeof(bridge));
bcnt=0;
for(i=1;i<=n;i++)
{
if(!pre[i])
{
bridge_search(i,0);
}
}
return bcnt;
}
int vis[maxn];
int dist[maxn];
void Dfs(int now,int num)
{
low[now]=num;
vis[now]=1;
int t,v,nn;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to,nn=e[0][t].num;
if(bridge[nn])
continue;
if(!vis[v])
{
Dfs(v,num);
}
}
}
void solve(int n)//Ëõµã
{
int i,sum=0;
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
{
if(!low[i])
Dfs(i,++sum);
}
for(i=1;i<=n;i++)
{
int t,v;
for(t=box[0][i];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(low[i]!=low[v])
{
add(low[i],low[v],0,1);
add(low[v],low[i],0,1);
}
}
}
}
void dfs(int now,int deep)
{
dist[now]=deep;
vis[now]=1;
int t,v;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(!vis[v])
{
dfs(v,deep+1);
}
}
}
int f[maxn];
void finit(int n)
{
int i;
for(i=0;i<=n;i++)
f[i]=i;
}
int find(int x)
{
if(x==f[x])
return x;
return f[x]=find(f[x]);
}
int ans[maxn];
void lca(int now)
{
f[now]=now;
vis[now]=1;
int t,v,x;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(!vis[v])
{
lca(v);
f[v]=now;
}
}
for(t=box[2][now];t+1;t=e[2][t].next)
{
v=e[2][t].to,x=e[2][t].num;
if(vis[v]==2)
{
int tt=find(v);
ans[x]=dist[now]+dist[v]-2*dist[tt];
}
}
vis[now]=2;
}
int main()
{
//freopen("dd.txt","r",stdin);
int n,m,i,a,b,q;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b,i,0);
add(b,a,i,0);
}
memset(ans,0,sizeof(ans));
Bridge(n);
solve(n);
memset(vis,0,sizeof(vis));
dfs(1,0);
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
if(low[a]!=low[b])
{
add(low[a],low[b],i,2);
add(low[b],low[a],i,2);
}
}
memset(vis,0,sizeof(vis));
lca(1);
for(i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
