\(ZJOI\) \(2004\) 嗅探器
一、题目大意
给出一张无向图以及两个点 \(root\) 和 \(ed\)，找出一个编号最小的并且在所有\(root\) 到 \(ed\) 的路径上的点。
二、解题思路
考虑缩点时的过程，设\(u\)是\(v\)的祖先，我们通过找\(v\)为根的搜索子树是否能延伸到时间戳小于\(u\)的节点来判断\(u\)是否为割点。如果该子树不能延伸至\(u\)以上，则去掉\(u\)后该子树会与其余部分 失去联系。
由此我们这样想：如果我们以一个信息中心\(root\)为根开始搜索，找到一个非根的割点\(u\)；此时若对应的子树根\(v\)的时间戳小于等于\(b\)的时间戳，则说明\(b\)存在于\(v\)的子树内。
这很显然，由于\(dfn\)随\(dfs\)序更新，若还没搜到\(b\)，则其\(dfn\)为\(0\)；或者\(dfn\)不为\(0\)而小于\(v\)，则说明\(b\)在进入\(v\)以前已经被搜到了。
那么如果把\(u\)断掉，\(v\)的整棵子树都会与根\(root\)失去联系，\(u\)就是所求的点之一。
算法只对原\(Tarjan\)函数的判断条件略做了修改，因此效率得到了极大保留，时间复杂度
\(O(n+m)\)
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 200010, M = N << 1;
int n;
bool st[N];
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int ans = INF;
int root, ed;
// Tarjan算法求割点
int dfn[N], low[N], ts;
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++ts;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
// u是割点
if (u != root && low[v] >= dfn[u]) {
if (u == ed) continue; // 根据题意，u必须在root和ed之间
if (dfn[ed] >= dfn[v]) ans = min(ans, u);
}
} else
low[u] = min(low[u], dfn[v]);
}
}
int main() {
// 初始化链式前向星
memset(h, -1, sizeof h);
scanf("%d", &n);
int x, y;
while (scanf("%d %d", &x, &y), x || y)
if (x != y) add(x, y), add(y, x);
scanf("%d %d", &root, &ed);
tarjan(root, -1); // 从其中一个信息中心开始遍历
if (ans == INF)
printf("No solution");
else
printf("%d", ans);
return 0;
}