NC51308. 逃不掉的路
描述
现代社会，路是必不可少的。
共有n个城镇，m条道路，任意两个城镇都有路相连，而且往往不止一条。
但有些路年久失修，走着很不爽。
按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从a城到b城不管怎么走，总有一些逃不掉的必经之路。
他想请你计算一下，a到b的所有路径中，有几条路是逃不掉的？
输入描述
第一行是n和m，用空格隔开。
接下来m行，每行两个整数x和y，用空格隔开，表示x城和y城之间有一条长为1的双向路。
第m+2行是q。
接下来q行，每行两个整数a和b，用空格隔开，表示一次询问。
输出描述
对于每次询问，输出一个正整数，表示a城到b城必须经过几条路。
每个输出占一行。
示例1
输入:
5 5 1 2 1 3 2 4 3 4 4 5 2 1 4 2 5
输出:
0 1
C++(g++ 7.5.0) 解法, 执行用时: 386ms, 内存消耗: 20716K, 提交时间: 2022-08-21 13:32:15
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct gg {
int y,next,v;
}a[N<<1],e[N<<1];
int tot=1,tc=1;
int n,m,q,x,y,num,dcc;
int d[N],f[N][25],dfn[N],low[N],lin[N],linc[N],bridge[N<<1],c[N];
inline void add(int x,int y) {
a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
}
inline void tarjan(int x,int in_edge) {
dfn[x]=low[x]=++num;
for(int i=lin[x];i;i=a[i].next) {
int y=a[i].y;
if(!dfn[y]) {
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]) {
bridge[i]=bridge[i^1]=1;
}
}
else if(i!=(in_edge^1))
low[x]=min(low[x],dfn[y]);
}
}
inline void dfs(int x) {
c[x]=dcc;
for(int i=lin[x];i;i=a[i].next) {
int y=a[i].y;
if(c[y]||bridge[i]) continue;
dfs(y);
}
}
inline void add_c(int x,int y) {
e[++tc].y=y; e[tc].next=linc[x]; linc[x]=tc;
}
inline void bfs() {
queue<int> q;
q.push(1);d[1]=1;
while(q.size()) {
int x=q.front();q.pop();
for(int i=linc[x];i;i=e[i].next) {
int y=e[i].y;
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=23;j++)
f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
}
inline int lca(int x,int y) {
if(d[x]>d[y]) swap(x,y);
for(int i=23;i>=0;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=23;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,-1);
for(int i=1;i<=n;i++)
{
if(!c[i])
{
++dcc;
dfs(i);
}
}
for(int i=2;i<=tot;i++)
{
int x=a[i^1].y,y=a[i].y;
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
add_c(c[y],c[x]);
}
bfs();
cin>>q;
while(q--)
{
cin>>x>>y;
x=c[x]; y=c[y];
printf("%d\n",d[x]+d[y]-2*d[lca(x,y)]);
}
return 0;
}
C++ 解法, 执行用时: 122ms, 内存消耗: 20344K, 提交时间: 2022-03-13 11:01:55
#include<bits/stdc++.h>
#define N 100010
#define M 200010
using namespace std;
int n,m,q;
struct rode
{
int y,next,p;
}e[2*M],tr[2*M];
struct node
{
int x,y;
}e1[2*M];
int len=1,cnt=0,vs=0;
int dfn[N],low[N],fl[N],fh[N];
int f[N][30],d[N];
int col[N];
void inc(int x,int y)
{
e[++len].y=y;
e[len].next=fl[x];
fl[x]=len;
}
void incc(int x,int y)
{
tr[++len].y=y;
tr[len].next=fh[x];
fh[x]=len;
}
void tarjan(int u,int ff)
{
dfn[u]=low[u]=++vs;
for(int i=fl[u];i;i=e[i].next)
{
int v=e[i].y;
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])
{
e[i].p=e[i^1].p=1;
}
}
else if(i!=(ff^1))
{
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int u)
{
col[u]=cnt;
for(int i=fl[u];i;i=e[i].next)
{
int v=e[i].y;
if(!col[v]&&!e[i].p)dfs(v);
}
}
void sd()
{
len=0;
for(int i=1;i<=m;++i)
{
int x=e1[i].x,y=e1[i].y;
incc(col[x],col[y]);
incc(col[y],col[x]);
}
}
void bfs()
{
queue<int>q;
q.push(1);d[1]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=fh[x];i;i=tr[i].next)
{
int y=tr[i].y;
if(d[y])
continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=18;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
int lca(int x,int y)
{
if(d[y]<d[x])swap(x,y);
for(int i=18;i>=0;i--)
{
if(d[f[y][i]]>=d[x])y=f[y][i];
}
if(x==y)
return x;
for(int i=18;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
scanf("%d%d",&n,&m);int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
inc(x,y);
inc(y,x);
e1[i].x=x;
e1[i].y=y;
}
tarjan(1,0);
for(int i=1;i<=n;++i)
{
if(!col[i])
{
++cnt;
dfs(i);
}
}
sd();
bfs();
scanf("%d",&q);
for(int i=1;i<=q;++i)
{
scanf("%d%d",&x,&y);
int t=lca(col[x],col[y]);
printf("%d\n",d[col[x]]+d[col[y]]-2*d[t]);
}
return 0;
}