题意：给出一张n个点m条边的无向图，然后又q组查询，询问从s节点走到m节点至少要经过多少条桥

思路：先dfs找桥，并给所有边-双连通分量蓝色。根据找到的桥以及桥的两端的节点的颜色，重新建图（每个节点代表一个双连通分量，其实就是形成一棵树），dfs一遍求各个点的深度，然后就是离线的求LCA，距离就是dis[u]+dis[v]-2*dis[LCA(u,v)]

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #define maxn 100010  7 using namespace std;  8   9 int pre[maxn],bccno[maxn],dfs_clock,bcc_cnt,bg_cnt; 10 int depth,dep[maxn],ancestor[maxn],f[maxn],vis[maxn],ans[maxn]; 11 pair
           
             bridge[maxn]; 12 vector
            
              G[maxn],g[maxn],qes[maxn],rank[maxn]; 13 stack
             
               S; 14 15 int dfs(int u,int fa){ 16 //printf("dfs(%d,%d)\n",u,fa); 17 int lowu = pre[u] = ++dfs_clock; 18 S.push(u); 19 for(int i = 0;i < G[u].size();i++){ 20 int v = G[u][i]; 21 if(!pre[v]){ 22 int lowv = dfs(v,u); 23 lowu = min(lowu,lowv); 24 if(lowv > pre[u]){ 25 bridge[bg_cnt++] = make_pair(u,v); 26 } 27 }else if(pre[v] < pre[u] && v != fa){ 28 lowu = min(lowu,pre[v]); 29 } 30 } 31 if(lowu == pre[u]){ 32 bcc_cnt++; 33 while(1){ 34 int x = S.top();S.pop(); 35 bccno[x] = bcc_cnt; 36 if(x == u) break; 37 } 38 } 39 return lowu; 40 } 41 42 void find_bcc(int n){ 43 memset(pre,0,sizeof(pre)); 44 dfs_clock = bg_cnt = bcc_cnt = 0; 45 dfs(1,-1); 46 } 47 48 void dfs2(int u,int fa,int d){ 49 //printf("dfs2(%d,%d,%d)\n",u,fa,d); 50 dep[u] = d; 51 for(int i = 0;i < g[u].size();i++){ 52 int v = g[u][i]; 53 if(v == fa) continue; 54 dfs2(v,u,d+1); 55 } 56 } 57 58 int find(int x){ 59 return x == f[x] ? x : f[x] = find(f[x]); 60 } 61 62 void LCA(int u,int fa){ 63 //printf("LCA(%d,%d)\n",u,fa); 64 ancestor[u] = u; 65 for(int i = 0;i < g[u].size();i++){ 66 int v = g[u][i]; 67 if(v == fa) continue; 68 LCA(v,u); 69 int fx = find(u),fy = find(v); 70 if(fx != fy) f[fx] = fy; 71 ancestor[find(u)] = u; 72 } 73 vis[u] = 1; 74 for(int i = 0;i < qes[u].size();i++){ 75 int v = qes[u][i]; 76 if(vis[v]){ 77 //printf("both ancestor of (%d,%d) is %d\n",u,v,ancestor[find(v)]); 78 int tmp = dep[u] + dep[v] - 2 * dep[ancestor[find(v)]]; 79 ans[rank[u][i]] = tmp; 80 } 81 } 82 } 83 84 int main(){ 85 int n,m,q; 86 while(scanf("%d%d",&n,&m) == 2){ 87 while(!S.empty()) S.pop(); 88 for(int i = 1;i <= n;i++) G[i].clear(); 89 for(int i = 0;i < m;i++){ 90 int a,b; 91 scanf("%d%d",&a,&b); 92 G[a].push_back(b); 93 G[b].push_back(a); 94 } 95 find_bcc(n); 96 //for(int i = 1;i <= n;i++){ 97 // printf("bccno[%d] = %d\n",i,bccno[i]); 98 //} 99 //printf("bg:\n");100 //for(int i = 0;i < bg_cnt;i++){101 // printf("%d %d bccno: %d %d\n",bridge[i].first,bridge[i].second,bccno[bridge[i].first],bccno[bridge[i].second]);102 //}103 for(int i = 1;i <= bcc_cnt;i++){104 g[i].clear();105 f[i] = i;106 vis[i] = 0;107 }108 for(int i = 0;i < bg_cnt;i++){109 int a = bridge[i].first;110 int b = bridge[i].second;111 g[bccno[a]].push_back(bccno[b]);112 g[bccno[b]].push_back(bccno[a]);113 }114 //for(int i = 1;i <= bcc_cnt;i++){115 // printf("g %d:\n",i);116 // for(int j = 0;j < g[i].size();j++)117 // printf("%d ",g[i][j]);118 // printf("\n");119 //}120 depth = 0;121 dfs2(1,-1,1);122 //for(int i = 1;i <= bcc_cnt;i++){123 // printf("dep[%d] = %d\n",i,dep[i]);124 //}125 scanf("%d",&q);126 for(int i = 0;i < q;i++){127 int a,b,x,y;128 scanf("%d%d",&x,&y);129 a = bccno[x];130 b = bccno[y];131 qes[a].push_back(b);132 qes[b].push_back(a);133 rank[a].push_back(i);134 rank[b].push_back(i);135 }136 LCA(1,-1);137 for(int i = 0;i < q;i++){138 printf("%d\n",ans[i]);139 }140 }141 return 0;142 }