题目内容
洛谷链接
给出一个(n)个节点，(m)条边的无向图和两个节点(s)和(t)，问这两个节点的路径中有几个点必须经过。
输入格式
第一行是(n)和(m)。
接下来(m)行，给出两个数表示这两个节点之间存在一条边。
接下来一行一个整数(Q)，表示询问个数。
接下来(Q)行，每行两个整数(s)和(t)((s
ot= t))。
数据范围
(0<nle 10000，0<mle 100000，0<Qle 10000，0<s,tle m)
输出格式
对于每个询问，输出一行表示答案
样例输入
5 6
1 2
1 3
2 3
3 4
4 5
3 5
2
2 3
2 4
0 0
样例输出
0
1
思路
这个题问的就是(s)到(t)路径上割点的个数。
点双缩点，可以知道，每条边仅在一个联通块中，把割点和它相邻的联通块建边，从而构造棵树。
询问(s)边和(t)边，需要求它们分别属于哪个连通块。所以问题转化成了一棵树中，有些点已标记为割点，询问两个非割点之间路径上有多少个割点。
因此选择一个点作为树根，求出每个点到树根路径上有多少个割点，然后对于询问的两个点求一次LCA即可。
代码
#include<cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=10000+10;
const int maxm=100000+10;
struct Edge{
int u,to,next,vis,id;
}edge[maxm<<1];
int head[maxn<<1],dfn[maxn<<1],low[maxn],st[maxm],iscut[maxn],subnet[maxn],bian[maxm];
int cnt,time,top,btot;
vector<int> belong[maxn];
void add(int u,int to){
edge[cnt].u=u;
edge[cnt].to=to;
edge[cnt].next=head[u];
edge[cnt].vis=0;
head[u]=cnt++;
}
void init(int n){
for(int i=0;i<=n;i++){
head[i]=-1;
dfn[i]=iscut[i]=subnet[i]=0;
belong[i].clear();
}
cnt=time=top=btot=0;
}
void dfs(int u){
dfn[u]=low[u]=++time;
for(int i=head[u];i!=-1;i=edge[i].next){
if(edge[i].vis)continue;
edge[i].vis=edge[i^1].vis=1;
int to=edge[i].to;
st[++top]=i;
if(!dfn[to]){
dfs(to);
low[u]=min(low[u],low[to]);
if(dfn[u]<=low[to]){
subnet[u]++;
iscut[u]=1;
btot++;
do{
int now=st[top--];
belong[edge[now].u].push_back(btot);
belong[edge[now].to].push_back(btot);
bian[edge[now].id]=btot;
to=edge[now].u;
}while(to!=u);
}
}
else
low[u]=min(low[u],low[to]);
}
}
int B[maxn<<2],F[maxn<<2],d[maxn<<2][20],pos[maxn<<2],tot,dep[maxn<<1];
bool treecut[maxn<<1];
void RMQ1(int n){
for(int i=1;i<=n;i++)d[i][0]=B[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+j-1<=n;i++)
d[i][j]=min(d[i][j-1],d[i + (1<<(j-1))][j-1]);
}
int RMQ(int L,int R){
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return min(d[L][k],d[R-(1<<k)+1][k] );
}
int lca(int a,int b){
if(pos[a] > pos[b])swap(a,b);
int ans=RMQ(pos[a],pos[b]);
return F[ans];
}
//写了个RMQ求LCA
void DFS(int u){
dfn[u]=++time;
B[++tot]=dfn[u];
F[time]=u;
pos[u]=tot;
for(int i=head[u];i!=-1;i=edge[i].next){
int to=edge[i].to;
if(!dfn[to]){
if(treecut[u])
dep[to]=dep[u] + 1;
else
dep[to]=dep[u];
DFS(to);
B[++tot]=dfn[u];
}
}
}
void solve(int n){
for(int i=0;i<=n;i++) {
dfn[i]=0;
}
time=tot=0;
for(int i=1;i<=n;i++)
if(!dfn[i]){
dep[i]=0;
DFS(i);
}
RMQ1(tot);
int m,u,to;
scanf("%d",&m);
while(m--){
scanf("%d%d",&u,&to);
u=bian[u];to=bian[to];
if(u<0||to<0){
printf("0
");continue;
}
int LCA=lca(u,to);
if(u==LCA)
printf("%d
",dep[to]-dep[u]-treecut[u]);
else if(to == LCA)
printf("%d
",dep[u]-dep[to]-treecut[to]);
else
printf("%d
",dep[u]+dep[to]-2*dep[LCA]-treecut[LCA]);
}
}
int main(){
int n,m,u,to;
while(scanf("%d%d",&n,&m)!=-1 && n){
init(n);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&to);
edge[cnt].id=i;
add(u,to);
edge[cnt].id=i;
add(to,u);
}
for(int i=1;i<=n;i++)
if(!dfn[i]){
dfs(i);
subnet[i]--;
if(subnet[i]<=0)iscut[i]=0;
}
int ditot=btot;
for(int i=1;i<=btot;i++)
treecut[i]=0;
for(int i=1;i<=btot+n;i++)
head[i]=-1;
cnt=0;
for(int i=1;i<=n;i++)
if(iscut[i]){
sort(belong[i].begin(),belong[i].end());
ditot++;
treecut[ditot]=1;
add(belong[i][0],ditot);
add(ditot,belong[i][0]);
for(int j=1;j<belong[i].size();j++)
if(belong[i][j]!=belong[i][j-1]){
add(belong[i][j],ditot);
add(ditot,belong[i][j]);
}
}
solve(ditot);
}
return 0;
}