题解：P3535 [POI2012] TOU-Tour de Byteotia

思路：

首先，由于我们只需要保证编号小于等于 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;
}