CF1133F2 Spanning Tree with One Fixed Degree 题解

Night_fall · 2023-08-31 21:07:02 · 题解

题目传送门

前置知识：并查集。

由于全程没有用搜索，所以自认为还是能提供一些新思路的吧。

看到题目，直接分两个部分：判断和连边。

判断部分

首先一个最简单的判定，与 1 节点相连的边数小于 D，直接输出 \texttt {NO}。

然后，我们可以使用连通块来判断。

这里连通块指的是去掉节点 1 后，相互连接的若干个节点。

显而易见，在每个连通块中必须有至少一个节点与节点 1 相连。

那么可以使用并查集计连通块个数，数量大于 D 输出 \texttt {NO}，否则为 \texttt{YES}。

连边部分

现将每个联通块中必连的一个边连好。

再根据 D 的大小从节点 1 连出其他边。

最后根据树的性质用并查集连出一棵树。个人认为这个过程类似于最小生成树。

其中 vis 数组表示该节点是否与 1 相连，f 数组表示连通块（前半段）或该点是否在树中（后半段）。

code

#include<iostream>
#include<algorithm>
using namespace std;

struct EDGE{int u,v,c;}e[200010];
int f[200010];
bool vis[200010];
int find(int x){return f[x]=(f[x]==x?x:find(f[x]));}

int main(){
    int n,m,d,cnt=0;
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v;
        if(e[i].u>e[i].v) swap(e[i].u,e[i].v); //规范化数据，便于代码编写
        if(find(e[i].u)!=find(e[i].v)&&e[i].u!=1) f[find(e[i].u)]=find(e[i].v); //统计连通块
        if(e[i].u==1) cnt++; //统计边数
    }
    if(cnt<d) puts("NO"),exit(0); //边数不够
    cnt=0;
    for(int i=2;i<=n;i++){
        if(f[i]==i) cnt++; //统计连通块个数
    }
    if(cnt>d) puts("NO"),exit(0); //连通块数量过多
    puts("YES");
    cnt=0;
    for(int i=1;i<=m;i++){
        if(f[find(e[i].v)]&&!vis[e[i].v]&&e[i].u==1) cnt++,cout<<"1 "<<e[i].v<<'\n',f[find(e[i].v)]=0,vis[e[i].v]=1;
    } //连接必连的边
    for(int i=1;i<=m&&cnt<d;i++){
        if(e[i].u==1&&!vis[e[i].v]) vis[e[i].v]=1,cout<<"1 "<<e[i].v<<'\n',cnt++;
    } //满足D的要求
    for(int i=1;i<=n;i++) f[i]=vis[i]?1:i; //统计节点是否已在树中（与1连接）
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        if(find(u)!=find(v)&&u!=1) f[find(u)]=find(v),printf("%d %d\n",u,v),cnt++;
        if(cnt==n-1) exit(0);
    } //最小生成树板子稍作修改
}