题意：
有一个n个点，m条边的图，没有重边、自环，且每一条边最多属于一个环路。
给出q组询问，每次询问u,v两点间的路径有多少种可能。
思路：
先看下方样例说明：
由样例说明可以得知，路径上每经过一个环，路径种数就会乘2，而且最终答案一定是2^n；
因此使用tarjan算法求出图中的环，由于题目限制，求点双联通分量和边双联通分量效果相同。因边双联通分量好写，懒惰的作者采用了它 -~_~-
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #include<vector> 9 #define ll long long 10 #define MOD 1000000007 11 using namespace std; 12 vector<int>a[100100],b[200100]; 13 stack<int>s; 14 int n,m,q,mm=0,dep[200100],dfn[100100],low[100100],fa[100100],p[200100][20],color[110100],times,cnt; 15 bool vis[100100],viss[200100]; 16 void tarjan(int u){ 17 int i,j,child=0,v; 18 s.push(u);vis[u]=1; 19 dfn[u]=low[u]=times++; 20 for(i=0;i<a[u].size();i++){ 21 v=a[u][i]; 22 if(!vis[v]){ 23 child++;fa[v]=u; 24 tarjan(v); 25 low[u]=min(low[u],low[v]); 26 } 27 else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); 28 } 29 if(dfn[u]==low[u]){ 30 cnt++; 31 int count=0,tmp; 32 while(!s.empty()){ 33 tmp=s.top(); 34 color[tmp]=cnt+n; 35 s.pop();count++; 36 if(tmp==u) break; 37 } 38 if(count==1) color[tmp]=tmp; 39 } 40 } 41 void dfs(int u){ 42 int i,v,t1,t2;t1=color[u]; 43 viss[t1]=1;vis[u]=1; 44 for(i=0;i<a[u].size();i++){ 45 v=a[u][i]; 46 t2=color[v]; 47 if(viss[t2]) goto skip; 48 mm++;p[t2][0]=t1;dep[t2]=dep[t1]+1; 49 b[t1].push_back(t2);b[t2].push_back(t1); 50 skip:if(vis[v]) continue; 51 dfs(v); 52 } 53 return; 54 } 55 void init(){ 56 int i,j; 57 for(j=1;j<20;j++){ 58 for(i=1;i<n+cnt;i++){ 59 if(!b[i].size()) continue; 60 p[i][j]=p[p[i][j-1]][j-1]; 61 } 62 } 63 } 64 void shrink(){ 65 int i,j; 66 for(i=1;i<=n;i++){ 67 if(!dfn[i]) tarjan(i); 68 } 69 memset(vis,0,sizeof(vis));memset(viss,0,sizeof(viss)); 70 dep[color[1]]=1;p[color[1]][0]=color[1];dfs(1); 71 init(); 72 return ; 73 } 74 ll calc(int k,int to){ 75 if(k==to) return (to>n)?2:1; 76 else return calc(p[k][0],to)*((k>n)?2:1); 77 } 78 ll lca(int l,int r){ 79 int i,lca,tl=l,tr=r; 80 if(dep[l]<dep[r]) swap(l,r); 81 int diff=dep[l]-dep[r]; 82 for(i=0;i<20;i++){ 83 if(diff&(1<<i)) l=p[l][i]; 84 } 85 if(l==r) lca=l; 86 else{ 87 for(i=19;i>=0;i--){ 88 if(p[l][i]!=p[r][i]){ 89 l=p[l][i];r=p[r][i]; 90 } 91 } 92 lca=p[l][0]; 93 } 94 return calc(tl,lca)*calc(tr,lca)/((lca>n)?2:1); 95 } 96 int main(){ 97 int i,t1,t2; 98 scanf("%d%d",&n,&m); 99 for(i=1;i<=n;i++) color[i]=i; 100 for(i=1;i<=m;i++){ 101 scanf("%d%d",&t1,&t2); 102 a[t1].push_back(t2);a[t2].push_back(t1); 103 } 104 shrink(); 105 scanf("%d",&q); 106 for(i=1;i<=q;i++){ 107 scanf("%d%d",&t1,&t2); 108 printf("%lld ",lca(color[t1],color[t2])%MOD); 109 } 110 }