自动搬运

查看原文

来自洛谷，原作者为

	liheyang123 「假装不在意，直到真的不在意」

搬运于2025-08-24 23:07:45，当前版本为作者最后更新于2025-07-04 10:20:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

赛时最初的想法（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;
}

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