edcc缩点之后跳倍增lca
丢个edcc缩点模板Code:
#include#include using namespace std;const int N = 1e5 + 5;const int M = 2e5 + 5;const int Lg = 25;int n, m, qn, tot = 1, head[N], dep[N], fa[N][Lg];int dfsc = 0, dcc = 0, dfn[N], low[N], bel[N], ex[M], ey[M];bool bri[M << 1], vis[N];struct Edge { int to, nxt;} e[M << 1];inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot;}inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}inline int min(int x, int y) { return x > y ? y : x;}void tarjan(int x, int inEdge) { dfn[x] = low[x] = ++dfsc; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(!dfn[y]) { tarjan(y, i); low[x] = min(low[x], low[y]); if(dfn[x] < low[y]) bri[i] = bri[i ^ 1] = 1; } else if(i != (inEdge ^ 1)) low[x] = min(low[x], dfn[y]); }}void dfs(int x) { bel[x] = dcc; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(bel[y] || bri[i]) continue; dfs(y); }}void dfs2(int x, int fat, int depth) { vis[x] = 1, fa[x][0] = fat, dep[x] = depth; for(int i = 1; i <= 20; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(vis[y]) continue; dfs2(y, x, depth + 1); } }void swap(int &x, int &y) { int t = x; x = y; y = t;}inline int getLca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 20; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 20; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0];}int main() { read(n), read(m); for(int i = 1; i <= m; i++) { read(ex[i]), read(ey[i]); add(ex[i], ey[i]), add(ey[i], ex[i]); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, 0); for(int i = 1; i <= n; i++) if(!bel[i]) { ++dcc; dfs(i); } /* for(int i = 1; i <= n; i++) printf("%d ", bel[i]); printf("\n"); */ tot = 0; memset(head, 0, sizeof(head)); for(int i = 1; i <= m; i++) { if(bel[ex[i]] == bel[ey[i]]) continue; add(bel[ex[i]], bel[ey[i]]), add(bel[ey[i]], bel[ex[i]]); } for(int i = 1; i <= n; i++) if(!vis[i]) dfs2(i, 0, 1); read(qn); for(int x, y; qn--; ) { read(x), read(y); x = bel[x], y = bel[y]; if(x == y) puts("0"); else printf("%d\n", dep[x] + dep[y] - 2 * dep[getLca(x, y)]); } return 0;}