题解：P11954 「ZHQOI R1」删边

wangtairan114 · 2025-03-22 19:55:10 · 题解

题目传送门

给一篇基于随机化的假做法。

思路

我们考虑对原图跑一遍生成树，对树上的每条边判断删掉该边是否合法。生成树剩下的边构成的图由两个点集组成，并且所有点度数不为零。由于边的顺序会影响我们生成树的形态，可以将边的顺序打乱，然后多做几遍。这样，我们有很大概率得到一组正解，输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3fll
#define IINF 0x3f3f3f3f
#define DINF 10000000
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define lowbit(x) ((x)&(-x))
int n,m;
const int N=500005;
vector<int> v[N];
pair<int,int> ed[N];
int fa[N];
int sum;
void init(){
    for(int i=1; i <= n; i++)
        fa[i]=i;
    sum=n;
}
int find(int x){
    return (fa[x]==x)?(fa[x]):(fa[x]=find(fa[x]));
}
vector<pair<int,int>> ans;
vector<int> g[N];
void merge(int x,int y){
    int fax=find(x),fay=find(y);
    if(fax==fay){//并查集
        ans.push_back({x,y});
        return;
    }
    g[x].push_back(y);
    g[y].push_back(x);
    fa[fax]=fay;
    sum--;
}
int sz[N];
void dfs1(int k,int f){
    sz[k]=1;
    for(auto y:g[k]){
        if(y==f)
            continue;
        dfs1(y,k);
        sz[k]+=sz[y];
    }
}
void dfs2(int k,int f){
    if(sz[1]-sz[k]>1&&sz[k]>1){
        ans.push_back({f,k});
        pr("%d\n",ans.size());
        for(auto y:ans)//得到一组解
            pr("%d %d\n",y.v1,y.v2);
        exit(0);
    }
    for(auto y:g[k]){
        if(y==f)
            continue;
        dfs2(y,k);
    }
}
void krus(){
    init();
    for(int i=1; i <= n; i++)
        g[i].clear();
    ans.clear();
    for(int i=1; i <= m; i++)//生成树
        merge(ed[i].v1,ed[i].v2);
    dfs1(1,0);
    dfs2(1,0);
}
int main(){
    sc("%d%d",&n,&m);
    for(int i=1; i <= m; i++){
        sc("%d%d",&ed[i].v1,&ed[i].v2);
        v[ed[i].v1].push_back(ed[i].v2);
        v[ed[i].v2].push_back(ed[i].v1);
    }
    std::random_device rd;
    std::mt19937 g(rd());
    for(int i=1; i <= 10; i++){
        shuffle(ed+1,ed+m+1,g);//随机化
        krus();
    }
    cout << -1;//无解输出-1
    return 0;
}