题意：给出一张n个点m条边的无向图，然后又q组查询，询问从s节点走到m节点至少要经过多少条桥
思路：先dfs找桥，并给所有边-双连通分量蓝色。根据找到的桥以及桥的两端的节点的颜色，重新建图（每个节点代表一个双连通分量，其实就是形成一棵树），dfs一遍求各个点的深度，然后就是离线的求LCA，距离就是dis[u]+dis[v]-2*dis[LCA(u,v)]
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <vector> 5 #include <algorithm> 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<int,int> bridge[maxn]; 12 vector<int> G[maxn],g[maxn],qes[maxn],rank[maxn]; 13 stack<int> S; 14 15 int dfs(int u,int fa){ 16 //printf("dfs(%d,%d) ",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) ",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) ",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 ",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 ",i,bccno[i]); 98 //} 99 //printf("bg: "); 100 //for(int i = 0;i < bg_cnt;i++){ 101 // printf("%d %d bccno: %d %d ",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: ",i); 116 // for(int j = 0;j < g[i].size();j++) 117 // printf("%d ",g[i][j]); 118 // printf(" "); 119 //} 120 depth = 0; 121 dfs2(1,-1,1); 122 //for(int i = 1;i <= bcc_cnt;i++){ 123 // printf("dep[%d] = %d ",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 ",ans[i]); 139 } 140 } 141 return 0; 142 }