HDU 3686 Traffic Real Time Query System(点双连通缩点 + LCA)
题意：
给你一个无向图，询问边a和边b，问从边a到边b的路径中几个点是必须要经过的。
解题思路：
很容易想到其实是求路径上割点的个数，然后就可以对图进行缩点了，我是把边缩成一个点(块)，因为每条边有且仅属于一个联通块中，然后对割点和它相邻的块建边，新的建边完成后新图就成了一棵树。询问a边和b边，只需要找出它们分别属于哪个块中，问题转化成：
一棵树中，有些点标记了是割点，现在询问两个不为割点的点路径上有多少个割点。
这样就很容易做了，以任意一个点为树根，求出每个点到树根路径上有多少个割点，然后对于询问的两个点求一次LCA就可以求出结果了，有点小细节不多说，自己画个图就清楚了。缩点后的树的点数可能为2*n级别的，要注意下。
具体见代码
#include <stdio.h>#include <vector>#include <algorithm>using namespace std;#define pb push_backconst int maxn = 10000 + 10; // 点的个数const int maxm = 100000 + 10; // 边的个数struct Edge { int u, to, next, vis, id;}edge[maxm<<1];int head[maxn<<1], dfn[maxn<<1], low[maxn], st[maxm], iscut[maxn], subnet[maxn], bian[maxm];int E, time, top, btot;vector<int> belo[maxn]; //点属于哪个块//加边void newedge(int u, int to) { edge[E].u = u; edge[E].to = to; edge[E].next = head[u]; edge[E].vis = 0; head[u] = E++;}void init(int n) { for(int i = 0;i <= n; i++) { head[i] = -1; dfn[i] = iscut[i] = subnet[i] = 0; belo[i].clear(); } E = time = top = btot = 0;}void dfs(int u) { dfn[u] = low[u] = ++time; for(int i = head[u];i != -1;i = edge[i].next) { if(edge[i].vis) continue; edge[i].vis = edge[i^1].vis = 1; int to = edge[i].to; st[++top] = i; if(!dfn[to]) { dfs(to); low[u] = min(low[u], low[to]); // 缩点成块 if(low[to] >= dfn[u]) { subnet[u]++; iscut[u] = 1; btot++; do { int now = st[top--]; belo[edge[now].u].pb(btot); belo[edge[now].to].pb(btot); bian[edge[now].id] = btot; // 记录某边属于哪个块 to = edge[now].u; }while(to != u); } } else low[u] = min(low[u], low[to]); }}int B[maxn<<2], F[maxn<<2], d[maxn<<2][20], pos[maxn<<2], tot, dep[maxn<<1];bool treecut[maxn<<1]; // 缩点成树后每个点是否为割点// RMQ 求lcavoid RMQ_init(int n) { for(int i = 1;i <= n; i++) d[i][0] = B[i]; for(int j = 1;(1<<j) <= n; j++) for(int i = 1;i + j - 1 <= n; i++) d[i][j] = min(d[i][j-1], d[i + (1<<(j-1))][j-1]);}int RMQ(int L, int R) { int k = 0; while((1<<(k+1)) <= R-L+1) k++; return min(d[L][k], d[R-(1<<k)+1][k] );}int lca(int a, int b) { if(pos[a] > pos[b]) swap(a, b); int ans = RMQ(pos[a], pos[b]); return F[ans];}// 搜树来构造RMQ LCAvoid DFS(int u) { dfn[u] = ++time; B[++tot] = dfn[u]; F[time] = u; pos[u] = tot; for(int i = head[u];i != -1;i = edge[i].next){ int to = edge[i].to; if(!dfn[to]) { if(treecut[u]) dep[to] = dep[u] + 1; else dep[to] = dep[u]; DFS(to); B[++tot] = dfn[u]; } }}void solve(int n) { for(int i = 0;i <= n; i++) { dfn[i] = 0; } time = tot = 0; for(int i = 1;i <= n; i++) if(!dfn[i]) { dep[i] = 0; DFS(i); } RMQ_init(tot); int m, u, to; scanf("%d", &m); while(m--) { scanf("%d%d", &u, &to); u = bian[u]; to = bian[to]; if(u < 0 || to < 0) { printf("0\n"); continue; } int LCA = lca(u, to); if(u == LCA) printf("%d\n", dep[to] - dep[u] - treecut[u]); else if(to == LCA) printf("%d\n", dep[u] - dep[to] - treecut[to]); else printf("%d\n", dep[u] + dep[to] - 2*dep[LCA] - treecut[LCA]); }}int main() { int n, m, u, to; while(scanf("%d%d", &n, &m) != -1 && n){ init(n); for(int i = 1;i <= m; i++) { scanf("%d%d", &u, &to); edge[E].id = i; newedge(u, to); edge[E].id = i; newedge(to, u); } for(int i = 1;i <= n;i ++) if(!dfn[i]) { dfs(i); subnet[i]--; if(subnet[i] <= 0) iscut[i] = 0; } int ditot = btot; // 树的总节点数 for(int i = 1;i <= btot; i++) treecut[i] = 0; for(int i = 1;i <= btot+n; i++) head[i] = -1; E = 0; for(int i = 1;i <= n; i++) if(iscut[i]) { sort(belo[i].begin(), belo[i].end()); ditot++; treecut[ditot] = 1; newedge(belo[i][0], ditot); newedge(ditot, belo[i][0]); // 割点与相邻块连边 for(int j = 1;j < belo[i].size(); j++) if(belo[i][j] != belo[i][j-1]) { newedge(belo[i][j], ditot); newedge(ditot, belo[i][j]); } } solve(ditot); } return 0;}