题解：P11483 [NordicOI 2021] The Elk

· · 题解

总结：缩点，然后搜索。显然在许多方面不同于写这篇题解时的其他题解。

赛时最初的想法（Flpp）：

考虑寻找 A 与 B 间的经过节点最多的简单路径，经过的点都是危险的，此处定义简单路径是不重复通过已经通过的边的路径。

注意到这是错的，显然也过于复杂，于是开始看特殊性质。

观察到 subtask#1 中，图退化成了树，这个非常重要，这时，A 与 B 间有且只有一条简单路径，即有且只有树链 (A,B) 上的点是危险的点。

接下来研究样例。

可以观察到在任意一个边双联通分量（环）内，任何一个点都可以经过环中所有的点后再次回到这个点，此处由 subtask#1 启发，应该考虑将图改成树，因此考虑 tarjan 缩点。

此处定义 \operatorname{bl(x)} 为点 x 所处的边双联通分量的编号。

然后关于求缩为树的图中链 (\operatorname{bl(A)},\operatorname{bl(B)}) 只需要 dfs 然后记录每一个在树链 (\operatorname{bl(A)},\operatorname{bl(B)}) 的边双联通分量 x 得前一个边双联通分量即可，然后标记树链上的边双联通分量，把非树链上的边双联通分量上的点记录、排序、输出即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read(){
    int s = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){ s = (s << 1) + (s << 3) + ch - '0'; ch = getchar();}
    return f * s;
}

const int N = 5e4 + 10;
const int M = 1e5 + 10;
int n, m, A, B;
int ver[M << 1], ne[M << 1], h[N], idx;
bool f[M << 1], vis[N];
void add(int u, int v){
    ver[idx] = v, ne[idx] = h[u];
    h[u] = idx++;
}
int dfn[N], low[N], times;
void tarjan(int u, int p){
    dfn[u] = low[u] = ++times;
    for(int i = h[u]; ~i; i = ne[i]){
        int to = ver[i];
        if(!dfn[to]){
            tarjan(to, i);
            low[u] = min(low[u], low[to]);
            if(low[to] > dfn[u]) {
                f[i] = f[i ^ 1] = 1;
            }
        }else if((i ^ 1) != p) low[u] = min(low[u], dfn[to]);
    }
}
vector<int> v[N];
int cnt, bl[N];
void dfs(int x){
    v[cnt].push_back(x); 
    vis[x] = 1;
    bl[x] = cnt;
    for(int i = h[x]; ~i; i = ne[i]){
        int to = ver[i];
        if(f[i]) continue;
        if(vis[to])continue;
        dfs(to);
    }
}
bool flaa[N];
vector<int> g[N], ans;
int r[N];
void dfs(int x, int p){
    for(int to : g[x]){
        if(to == p)continue;
        r[to] = x;
        dfs(to, x);
    }
}
int main() {
    memset(h, -1, sizeof h);
    n = read(), m = read(), A = read() + 1, B = read() + 1;
    for(int i = 1; i <= m; i++){
        int u = read() + 1, v = read() + 1;
        add(u, v);
        add(v, u); 
    }
    for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, -1);
    for(int i = 1; i <= n; i++) if(!vis[i]){ cnt++; dfs(i);}

    for(int i = 1; i <= cnt; i++){
        for(int x : v[i]) {
            for(int i = h[x]; ~i; i = ne[i]){
                int to = ver[i];
                if(bl[to] != bl[x]) g[bl[x]].emplace_back(bl[to]);
            }
        //  cout<<x<<' '<<bl[x]<<' ';
        }//cout<<'\n';
    }
    dfs(bl[A], 0);
    for(int t = bl[B]; t; t = r[t]) flaa[t] = 1;//cout<<t<<' ';
    for(int i = 1; i <= cnt; i++){
        if(flaa[i]) continue;
        for(int x : v[i]) {
            ans.push_back(x);
        }
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for(int x : ans) printf("%d\n", x - 1);
    return 0;
}

不建议直接参考这份代码。