自动搬运

查看原文

来自洛谷，原作者为

	Dream_poetry 锁阁自此隽长永，孤影凭梦绘常恒。 || 孤举敬卿花间酒，盼君余载尽欢春 || 一别复还阻且漫，云念君瞳拨青岚 || 缕缕幽籁余音浅，明灭烛星殿前欢

搬运于2025-08-24 21:49:57，当前版本为作者最后更新于2024-11-15 20:27:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

首先，由于我们只需要保证编号小于等于 $k$ 的点不在简单环上，这就意味着两个编号大于 $k$ 的点之间的连边是没有必要删除的，因为假如有一个编号小于等于 $k$ 的点在一个简单环上，我们肯定可以通过删除一条与这个点相连的边使得这个环消失，所以我们直接删除一条与这个编号小于等于 $k$ 的点相连的边使得它脱离这个环显然是不劣的。

所以，必然有一组最优解保留了所有大于 $k$ 的点相互之间的连边。因此我们直接保留这些边即可。

然后将这些边所连的点通过并查集归在一起，方便后续判环。

然后枚举每一条边，如果这条边所连的两个点有一个的编号小于等于 $k$，那么我们就考虑保留这条边是否会产生环，否则直接跳过即可。

如果保留这条边会产生环，那我们必然舍弃，计入答案即可。

那如果保留这条边不会产生环，我们是否要保留呢？

其实此时问题可以转化为 $k$ 个独立点和若干个连通块，每个独立点和每个连通块之间最多只能连一条边。

那么显然我们肯定是要能连尽量连，这样才能保证删除的边最少。

当上述情况发生时，其实就相当于一个独立点和一个连通块第一次尝试连边，那么由于我们无法保证后续是否会出现新的边来把这两部分连起来，为保证最优性，我们肯定是要保留这条边的。

至此，思路显然了，代码也就简单了，利用并查集判环即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int k;

struct node{
	int x,y;
};
node e[2000005];
node ans[2000005];

int fa[1000005];
int cnt;


inline int find(int x){
	if (fa[x]!=x){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}


signed main(){
	ios::sync_with_stdio(0);
	
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	for (int i=1;i<=n;i++){
	    fa[i]=i;
	}
	cin>>k;
	for (int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y;
		if (e[i].x>k && e[i].y>k){
			fa[find(e[i].x)]=find(e[i].y);
		}
	}
	for (int i=1;i<=m;i++){
		int u=find(e[i].x);
		int v=find(e[i].y);
		if (e[i].x<=k || e[i].y<=k){
			if (u==v){
				cnt++;
				ans[cnt]=e[i];
			}
			else{
			    fa[u]=v;
			}
		}
	}
	cout<<cnt<<"\n";
	for (int i=1;i<=cnt;i++){
		if (ans[i].x<ans[i].y){
			cout<<ans[i].x<<' '<<ans[i].y<<"\n";
		}
		else{
			cout<<ans[i].y<<' '<<ans[i].x<<"\n";
		}
	}
	return 0;
}