tarjan
这题数据范围是可以 \(O(n^3)\) 暴力过的……
显然只需缩点后的树上 \(bl_s\) 到 \(bl_t\) 上找答案，统计割点贡献即可
然而此题有更简单的做法……
从 \(s\) 开始 tarjan，点 \(u\) 对答案有贡献当且仅当满足以下四个条件：
- \(u\neq s,\ t\)
- \(cut_u=\operatorname{true}\)
- \(dfn_v\leq dfn_t\) ，因为终点必须在 \(u\) 之后访问到
- \(dfn_u\leq low_t\) ，因为路径必须要经过 \(u\) 点
然后上板子
时间复杂度 \(O(n+m)\)
这份代码是缩点后统计链的……
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110, inf = INT_MAX;
bool cut[maxn];
int n, m, A, B, h[maxn], q[maxn << 1], pre[maxn << 1];
int top, dcc, tot, st[maxn], bl[maxn], dfn[maxn], low[maxn];
struct edges {
int nxt, to;
edges(int x = 0, int y = 0) :
nxt(x), to(y) {}
} e[maxn * maxn * 2];
vector <int> E[maxn << 1], d[maxn];
void addline(int u, int v) {
static int cnt;
e[++cnt] = edges(h[u], v), h[u] = cnt;
}
void tarjan(int u, int f) {
static int now;
st[++top] = u;
dfn[u] = low[u] = ++now;
if (!f && !h[u]) {
d[++dcc].push_back(u);
return;
}
for (int i = h[u], chd = 0; i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
tarjan(v, 1);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
cut[u] |= f || chd++;
for (dcc++; st[top + 1] != v; top--) {
d[dcc].push_back(st[top]);
}
d[dcc].push_back(u);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
int bfs(int S, int T) {
if (S == T) return inf;
int l = 1, r = 1;
q[1] = S, pre[S] = -1;
while (l <= r) {
int u = q[l++];
for (int v : E[u]) {
if (!pre[v]) {
q[++r] = v, pre[v] = u;
}
}
}
int res = inf;
for (int u = pre[T]; u != S; u = pre[u]) {
if (u > dcc) res = min(res, u);
}
return res;
}
int main() {
scanf("%d", &n);
int u, v;
while (scanf("%d %d", &u, &v) && u && v) {
addline(u, v), addline(v, u);
}
scanf("%d %d", &A, &B);
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, 0);
}
tot = dcc;
for (int i = 1; i <= n; i++) {
if (cut[i]) bl[i] = ++tot;
}
for (int i = 1; i <= dcc; i++) {
for (int j = 0, _sz = int(d[i].size()); j < _sz; j++) {
int x = d[i][j];
if (cut[x]) {
E[i].push_back(bl[x]);
E[bl[x]].push_back(i);
} else {
bl[x] = i;
}
}
}
int res = bfs(bl[A], bl[B]);
if (res > 1e9) {
puts("No solution");
} else {
for (int i = 1; i <= n; i++) {
if (cut[i] && bl[i] == res) {
printf("%d", i); break;
}
}
}
return 0;
}