村长要召开羊族大会，讨论羊族未来的发展，要求羊羊们到指定地点集合。小羊们收到通知后从家里出发到达指定地点。每个羊的家都是与其他羊的家连通的，可以互相访问。 比如说可以从1到3，同样也可以从3到1 。灰太郎听到这个消息后，准备有所行动（你懂的）。但他不知道应该在哪条路上等羊。但他知道，有的路线一定要进过某条边。如上图从1到5一定要经过4-5这条路，这样他可以在那条路上事先埋伏好。现在他想知道2个点之间有多少这样的路。如果没有输出0.
Input
第一行有两个整数N，M。表示有N(1<N<10001)个家，M(1<M<10001)条路线。随后有M行，每行有两个不相同的整数A、B表示 A,B之间有一条路。我们保证任意时刻任意两个地点都能够相互到达并且2点之间最多只有1条路。接下来输入一个数K(K<20001)表示有K次查询。随后有K行。 每行有两个不相同的整数A、B询问 A,B之间有多少条的那样的路。
Output
对于每个询问输出有多少条那样的路。
Sample Input
5 5 1 2 3 4 2 4 3 1 5 4 4 1 5 3 5 2 3 4 1
Sample Output
1 1 0 0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//求任意两点之间的必经之路
//求桥边
//缩点
//求LCA
///此题中没有重边
const int maxn=30000;
struct fedge
{
int t,index;
int next;
};
int V,E;
int p[maxn];
fedge G[maxn*2];
int l;
void init()
{
memset(p,-1,sizeof(p));
l=0;
}
void addedge(int u,int t,int index,int l)
{
G[l].t=t;
G[l].index=index;
G[l].next=p[u];
p[u]=l;
}
int isbridge[maxn];
//tarjan 求割点 割边(没有重边)
int cut[maxn];//cut[i]非0表示i是割点
int color[maxn];//颜色:0表示没有访问,1表示正在访问,2表示访问结束
int lowc[maxn];//表示i及i的子孙相连的辈分最高的祖先节点所在的深度
int d[maxn];//表示i节点在树中的深度
int root;//根节点
int fath;//父节点
int pcnt;//割点个数
int egcnt;//割边个数
int egt[maxn];
int egu[maxn];
int egv[maxn];
void dfs(int u,int fath,int deep)
{
color[u]=1;//正在访问
lowc[u]=d[u]=deep;//深度
int tot=0;//子树个数
for(int i=p[u];i!=-1;i=G[i].next)
{
int t=G[i].t,index=G[i].index;
if(t!=fath&&color[t]==1)
{
lowc[u]=min(lowc[u],d[t]);
}
if(color[t]==0)
{
dfs(t,u,deep+1);
tot++;//子树加1
lowc[u]=min(lowc[u],lowc[t]);
//求割点
//if((u==root&&tot>1)||(u!=root&&lowc[t]>=d[u])) cut[u]=1;//不能将pscnt++写到这里
//求割边
if(lowc[t]>d[u]) //edge[u][t]=true; u->t是割边
{
//判断重边
egu[egcnt]=u;
egv[egcnt]=t;
egt[egcnt++]=index;
isbridge[index]=1;
}
}
}
color[u]=2;
}
void calc()
{
pcnt=egcnt=0;
memset(color,0,sizeof(color));
memset(lowc,0,sizeof(lowc));
memset(d,0,sizeof(d));
memset(cut,0,sizeof(cut));
root=1;
dfs(1,-1,1);
//for(int i=1;i<=V;i++) if(cut[i]) pcnt++;
}
//去掉桥边 缩点
int tp[maxn];
fedge tG[maxn*2];
int tl;
void taddedge(int u,int t,int index,int l)
{
tG[l].t=t;
tG[l].index=index;
tG[l].next=tp[u];
tp[u]=l;
}
int vis[maxn];
int belg[maxn];//节点i属于第几块
void find(int u,int id)
{
vis[u]=1;belg[u]=id;
for(int i=p[u];i!=-1;i=G[i].next)
{
int t=G[i].t,index=G[i].index;
if(!isbridge[index]&&!vis[t])
{
find(t,id);
}
}
}
int det;//缩点后节点个数
void rebuildgraph()
{
memset(tp,-1,sizeof(tp));
tl=0;
det=0;
memset(vis,0,sizeof(vis));
memset(belg,0,sizeof(belg));
for(int i=1;i<=V;i++)
{
if(!vis[i])
{
find(i,++det);
}
}
//求LCA中会加上桥边
/*for(int i=0;i<egcnt;i++)//缩点后再加上桥边
{
int u=egu[i],v=egv[i];
int tu=belg[u],tv=belg[v];
taddedge(tu,tv,i+1,tl++);
// taddedge(tv,tu,i+1,tl++);
}*/
}
//RMQ求LCA
const int N = 11005;
const int M = 101;
const int MAX = 10000000;
int n;
struct Edge
{
int u,v,next;
}edge[N*2];
int head[N],tot = 0;
void addedge(int u, int v)
{
tot++;
edge[tot].u = u;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
int first[N];//结点在搜索顺序数组中最先出现的位置（下标）
int occur[2*N];//结点在出现的顺序数组重复的也要记录
int depth[2*N];//结点在搜索树中的深度，与occur相对应
int dp_min[2*N][20];//dp_min[i][j] 表示从第i个位置开始的2^j个元素中的最小值的下标
int m ;//不断记录出现的下标
void rdfs(int u, int deep,int fath)
{
occur[++m] = u;//进入该点时进行记录
depth[m] = deep;
if(!first[u])
{
first[u] = m;
}
for(int i = head[u]; i != 0; i = edge[i].next)
{
if(edge[i].v==fath) continue;
rdfs(edge[i].v, deep+1,u);
occur[++m] = u;//访问子树返回也要标记
depth[m] = deep;
}
}
int lev[maxn];
void calclevel(int u,int fath)
{
for(int i=head[u];i!=0;i=edge[i].next)
{
int t=edge[i].v;
if(t==fath) continue;
lev[t]=lev[u]+1;
calclevel(t,u);
}
}
void rinit()
{
tot = 0;
m = 0;
memset(head,0,sizeof(head));
memset(first,0,sizeof(first));
int u,v;
//cin>>n;
n=det;
/*for(int i = 1; i < n; i++)
{
cin>>u>>v;
addedge(u,v);
in[v] = true;
}*/
for(int i=0;i<egcnt;i++)//建树
{
int u=egu[i],v=egv[i];
int tu=belg[u],tv=belg[v];
addedge(tu,tv);
addedge(tv,tu);
}
lev[1]=0;
calclevel(1,-1);
rdfs(1,1,-1);
}
void rmq_init()
{
for(int i = 1; i <= m; i++)
{
dp_min[i][0] = i;
}
for(int j = 1,s = 1; s <= m; s = (1<<(j++)))
{
for(int i = 1; i+s < m; i++)
{//由于要求的是最小值的下标这里采用间接比较，将长为s的区间分为相等的两端求最小值，以2的幂不断增加s，最终的解
dp_min[i][j] = depth[dp_min[i][j-1]] < depth[dp_min[i+s][j-1]] ? dp_min[i][j-1] : dp_min[i+s][j-1];
}
}
}
int rmq_min(int a, int b)
{
int l=first[a],r=first[b];//得到区间的左右端点
if(l > r)
{
int t = l;
l = r;
r = t;
}
int k = floor(log(double(r-l+1))/log(2.0));
int s = 1<<k;
int min_id = depth[dp_min[l][k]] < depth[dp_min[r-s+1][k]] ? dp_min[l][k] : dp_min[r-s+1][k];
return occur[min_id];
}
int main()
{
while(scanf("%d%d",&V,&E)==2)
{
init();
memset(isbridge,0,sizeof(isbridge));
for(int i=1;i<=E;i++)
{
int u,t,index=i;
scanf("%d%d",&u,&t);
u++,t++;
addedge(u,t,index,l++);
addedge(t,u,index,l++);
}
calc();
//删除桥边 缩点
rebuildgraph();
rinit();
rmq_init();
int q;scanf("%d",&q);
while(q--)
{
int s,t;scanf("%d%d",&s,&t);
s++,t++;
s=belg[s],t=belg[t];//缩点后的图
int la=rmq_min(s,t);
printf("%d\n",lev[s]+lev[t]-lev[la]*2);
}
}
return 0;
}