Input There are multiple test cases.
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi).
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: 0<N<=10000, 0<M<=100000, 0<Q<=10000, 0<Xi,Yi<=N, 0<S,T<=M
Output For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass. Sample Input 5 6 1 2 1 3 2 3 3 4 4 5 3 5 2 2 3 2 4 0 0 Sample Output 0 1 ——————————————————————————————————————————————————————————————————
给你一个无向图,询问边a和边b,问从边a到边b的路径中几个点是必须要经过的。
题解
求无向图的必经点,跟上题类似,求出点双后缩点,然后转化成查询路径上割点的个数。由于点双缩点的特殊性,所以算距离的时候写的不一样。
后面就是代码了:
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #define rg register 5 #define il inline 6 #define co const 7 template<class T>il T read(){ 8 rg T data=0,w=1;rg char ch=getchar(); 9 for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w; 10 for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0'; 11 return data*w; 12 } 13 template<class T>il T read(rg T&x) {return x=read<T>();} 14 typedef long long ll; 15 using namespace std; 16 17 co int N=2e4+1,M=2e5+2; 18 int n,m,t; 19 int head[N],ver[M],next[M],tot; 20 int dfn[N],low[N],stack[N],new_id[N],c[N],belong[M],num,root,top,cnt; 21 int d[N],dist[N],f[N][16]; 22 bool cut[N]; 23 vector<int> dcc[N]; 24 int hc[N],vc[M],nc[M],tc; 25 queue<int> q; 26 27 il void add(int x,int y){ 28 ver[++tot]=y,::next[tot]=head[x],head[x]=tot; 29 } 30 il void add_c(int x,int y){ 31 vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc; 32 } 33 void tarjan(int x){ 34 dfn[x]=low[x]=++num; 35 stack[++top]=x; 36 if(x==root&&head[x]==0){ 37 dcc[++cnt].push_back(x); 38 return; 39 } 40 int flag=0; 41 for(int i=head[x];i;i=::next[i]){ 42 int y=ver[i]; 43 if(!dfn[y]){ 44 tarjan(y); 45 low[x]=min(low[x],low[y]); 46 if(low[y]>=dfn[x]){ 47 ++flag; 48 if(x!=root||flag>1) cut[x]=1; 49 ++cnt; 50 int z; 51 do{ 52 z=stack[top--]; 53 dcc[cnt].push_back(z); 54 }while(z!=y); 55 dcc[cnt].push_back(x); 56 } 57 } 58 else low[x]=min(low[x],dfn[y]); 59 } 60 } 61 void bfs(int s){ 62 d[s]=1,dist[s]=s>cnt,q.push(s); 63 for(int i=0;i<16;++i) f[s][i]=0; 64 while(q.size()){ 65 int x=q.front();q.pop(); 66 for(int i=hc[x];i;i=nc[i]){ 67 int y=vc[i]; 68 if(d[y]) continue; 69 d[y]=d[x]+1,dist[y]=dist[x]+(y>cnt),f[y][0]=x; 70 for(int j=1;j<16;++j) f[y][j]=f[f[y][j-1]][j-1]; 71 q.push(y); 72 } 73 } 74 } 75 int lca(int x,int y){ 76 if(d[x]<d[y]) swap(x,y); 77 for(int i=15;i>=0;--i) 78 if(d[f[x][i]]>=d[y]) x=f[x][i]; 79 if(x==y) return x; 80 for(int i=15;i>=0;--i) 81 if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 82 return f[x][0]; 83 } 84 int main(){ 85 while(read(n)|read(m)){ 86 memset(head,0,sizeof head); 87 memset(hc,0,sizeof hc); 88 memset(dfn,0,sizeof dfn); 89 memset(d,0,sizeof d); 90 memset(cut,0,sizeof cut); 91 memset(c,0,sizeof c); 92 for(int i=1;i<=n;++i) dcc[i].clear(); 93 tot=1,num=cnt=top=0; 94 for(int x,y;m--;){ 95 read(x),read(y); 96 add(x,y),add(y,x); 97 } 98 for(int i=1;i<=n;++i) 99 if(!dfn[i]) root=i,tarjan(i); 100 num=cnt; 101 for(int i=1;i<=n;++i) 102 if(cut[i]) new_id[i]=++num; 103 tc=1; 104 for(int i=1;i<=cnt;++i){ 105 for(int j=0;j<dcc[i].size();++j){ 106 int x=dcc[i][j]; 107 if(cut[x]) add_c(i,new_id[x]),add_c(new_id[x],i); 108 c[x]=i; 109 } 110 for(int j=0;j<dcc[i].size()-1;++j){ 111 int x=dcc[i][j]; 112 for(int k=head[x];k;k=::next[k]){ 113 int y=ver[k]; 114 if(c[y]==i) belong[k/2]=i; // 输入的第k/2条边(x,y)处于第i个v-DCC内 115 } 116 } 117 } 118 // 编号 1~cnt 的为原图的v-DCC,编号 cnt+1~num 的为原图割点 119 for(int i=1;i<=num;++i) 120 if(!d[i]) bfs(i); 121 read(t); 122 while(t--){ 123 int es=read<int>(),et=read<int>(); 124 int x=belong[es],y=belong[et],z=lca(x,y); 125 printf("%d\n",dist[x]+dist[y]-2*dist[z]+(z>cnt)); 126 } 127 } 128 return 0