题目大意：
有一张无向连通图，问从一条边走到另一条边必定要经过的点有几个。
思路：
先用tarjan将双连通分量都并起来，剩下的再将割点独立出来，建成一棵树，之后记录每个点到根有几个割点，再用RMQ求LCA计算。
注意：数组范围。
代码：
1 #include<cstdio> 2 #include<vector> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int N=10009,M=100009; 7 int u[M<<1],v[M<<1],nex[M<<1],id[M<<1],hea[N<<1],dfn[N<<1],low[N],st[M],sub[N],edge[M], 8 fa[N<<2][20],f[N<<2],pos[N<<2],dep[N<<1]; 9 bool vis[M<<1],iscut[N],treecut[N<<1]; 10 int tim,top,tot,cnt,num; 11 vector <int> belo[N]; 12 13 int read() 14 { 15 int x=0; char ch=getchar(); 16 while (ch<'0' || ch>'9') ch=getchar(); 17 while (ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 18 return x; 19 } 20 21 void add(int x,int y) { v[cnt]=y,u[cnt]=x,nex[cnt]=hea[x],vis[cnt]=0,hea[x]=cnt++; } 22 23 void tarjan(int x) 24 { 25 dfn[x]=low[x]=++tim; 26 for (int i=hea[x];~i;i=nex[i]) 27 if (!vis[i]) 28 { 29 int y=v[i]; st[++top]=i; 30 vis[i]=vis[i^1]=1; 31 if (!dfn[y]) 32 { 33 tarjan(y); 34 low[x]=min(low[x],low[y]); 35 if (low[y]>=dfn[x]) 36 { 37 ++sub[x],++num; 38 iscut[x]=1; 39 do 40 { 41 int now=st[top--]; 42 belo[u[now]].push_back(num); 43 belo[v[now]].push_back(num); 44 edge[id[now]]=num; 45 y=u[now]; 46 }while (y^x); 47 } 48 } 49 else low[x]=min(low[x],dfn[y]); 50 } 51 } 52 53 void dfs(int x) 54 { 55 dfn[x]=++tim; fa[++tot][0]=dfn[x]; 56 f[tim]=x; pos[x]=tot; 57 for (int i=hea[x];~i;i=nex[i]) 58 { 59 int y=v[i]; 60 if (!dfn[y]) 61 { 62 dep[y]=dep[x]+treecut[x]; 63 dfs(y); fa[++tot][0]=dfn[x]; 64 } 65 } 66 } 67 68 void RMQ(int n) 69 { 70 for (int j=1;(1<<j)<=n;++j) 71 for (int i=1;i+j-1<=n;++i) 72 fa[i][j]=min(fa[i][j-1],fa[i+(1<<j-1)][j-1]); 73 } 74 75 int lca(int x,int y) 76 { 77 if (pos[x]<pos[y]) swap(x,y); 78 int k=0; 79 while (1<<(k+1)<=pos[x]-pos[y]+1) ++k; 80 return f[min(fa[pos[y]][k],fa[pos[x]-(1<<k)+1][k])]; 81 } 82 83 void wk(int n) 84 { 85 int i,m,x,y; 86 for (tim=tot=i=0;i<=n;++i) dfn[i]=0; 87 for (i=1;i<=n;++i) 88 if (!dfn[i]) dep[i]=0,dfs(i); 89 RMQ(tot); 90 for (m=read();m--;) 91 { 92 x=edge[read()],y=edge[read()]; 93 if (x<0 || y<0) { puts("0"); continue; } 94 int z=lca(x,y); 95 if (x==z) printf("%d\n",dep[y]-dep[x]-treecut[x]); 96 else if (y==z) printf("%d\n",dep[x]-dep[y]-treecut[y]); 97 else printf("%d\n",dep[x]+dep[y]-(dep[z]<<1)-treecut[z]); 98 } 99 } 100 101 int main() 102 { 103 int n,m; 104 while (~scanf("%d%d",&n,&m)) 105 { 106 int i; cnt=top=num=tim=0; 107 if (!(n+m)) break; 108 for (i=0;i<=n;++i) hea[i]=-1,dfn[i]=sub[i]=iscut[i]=0,belo[i].clear(); 109 for (i=1;i<=m;++i) 110 { 111 int x=read(),y=read(); 112 id[cnt]=i,add(x,y),id[cnt]=i,add(y,x); 113 } 114 for (i=1;i<=n;++i) 115 if (!dfn[i]) 116 { 117 tarjan(i); 118 if (--sub[i]<=0) iscut[i]=0; 119 } 120 for (i=1;i<=num;++i) treecut[i]=0; 121 for (i=1;i<=num+n;++i) hea[i]=-1; 122 cnt=0; 123 for (i=1;i<=n;++i) 124 if (iscut[i]) 125 { 126 sort(belo[i].begin(),belo[i].end()); 127 treecut[++num]=1; 128 add(belo[i][0],num),add(num,belo[i][0]); 129 for (int j=1;j<belo[i].size();++j) 130 if (belo[i][j]^belo[i][j-1]) add(belo[i][j],num),add(num,belo[i][j]); 131 } 132 wk(num); 133 } 134 return 0; 135 }
转载于:https://www.cnblogs.com/HHshy/p/6159332.html
相关资源：JAVA上百实例源码以及开源项目