Bubble Cup 11 - Finals [Online Mirror, Div. 2] B. Hyperspace Highways（tarjan - 点双连通分量 + LCA）

题目链接：http://codeforces.com/contest/1046/problem/B

题目大意：给出一个n个点，m条边的无向图，这个图有一个特殊的性质是，图中任意一个环内都是一个完全子图。

接下来有q次询问，每次询问给出两个点u和v，要你求出从u走到v最少需要经过几条边。

题目思路：解决本题的关键是题目中所给出的一个条件：图中任意一个环内都是一个完全子图。

这个条件意味着，图中任意一个点双联通分量内的点的距离都是1。这样我们就可以用tarjan算法对这个图进行缩点建图，找出图中所有的割顶，再加入新的节点变成割顶。

缩完点之后的图就变成一棵树了，接下来要求两点之间的距离的话，就变成求树上两点之间的距离了，只需要借助LCA就能求解了。

通过点双连通分量的性质，我们知道缩完点后的图，原来的节点之间不存在边，每个节点都会向自己所属的联通分量的割顶连边，所以在这棵树上的距离是原来距离的两倍，最后答案再除以2就行了。

具体实现看代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define lowbit(x) x&-x
#define clr(a) memset(a,0,sizeof(a))
#define _INF(a) memset(a,0x3f,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define IOS ios::sync_with_stdio(false)
#define fuck(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MX = 1e5 + 7;

int n, m, q;
int low[MX], dfn[MX], stk[MX], dsz, ssz, bsz;
int dep[MX << 1], ST[MX << 1][21];
vector<int>E[MX], G[MX << 1];

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++dsz;
	stk[++ssz] = u;
	for (auto v : E[u]) {
		if (v == fa) continue;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				++bsz;
				int now;
				do {
					now = stk[ssz--];
					G[bsz].pb(now); G[now].pb(bsz);
				} while (now != v);
				G[bsz].pb(u); G[u].pb(bsz);
			}
		} else
			low[u] = min(low[u], dfn[v]);
	}
}

void dfs(int u, int fa, int d) {
	dep[u] = d; ST[u][0] = fa;
	for (int i = 1; i <= 20; i++)
		ST[u][i] = ST[ST[u][i - 1]][i - 1];
	for (auto v : G[u]) {
		if (v == fa) continue;
		dfs(v, u, d + 1);
	}
}
int LCA(int u, int v) {
	while (dep[u] != dep[v]) {
		if (dep[u] < dep[v]) swap(u, v);
		int d = dep[u] - dep[v];
		for (int i = 0; i <= 20; i++)
			if ((d >> i) & 1) u = ST[u][i];
	}
	if (u == v) return u;
	for (int i = 20; i >= 0; i--) {
		if (ST[u][i] != ST[v][i]) {
			u = ST[u][i];
			v = ST[v][i];
		}
	}
	return ST[u][0];
}
void pre_solve() {
	bsz = n;
	tarjan(1, 0);
	dfs(1, 0, 1);
}

int main() {
	// FIN;
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < m; i++) {
		int u, v; scanf("%d%d", &u, &v);
		E[u].pb(v); E[v].pb(u);
	}
	pre_solve();
	while (q--) {
		int u, v;
		scanf("%d%d", &u, &v);
		int lca = LCA(u, v);
		int ans = dep[u] + dep[v] - 2 * dep[lca];
		ans >>= 1;
		printf("%d\n", ans);
	}
	return 0;
}