题解：P11486 「Cfz Round 5」Mata rainen

de_mosyt · 2024-12-29 19:05:35 · 题解

思路：

首先要判断是否可以建符合题目要求的树，显然，当图中存在环时，不能成为树，因此我们想到使用并查集维护，当输入的两个点的祖先相同时，因为这两个点还会连接，所以一定会成环，此时就结束掉程序；否则就可以建树。

因为这个题目中每条边都只被给出点的最短路径经过了一遍，因此，我们先将输入的点对直接建边（如下图蓝点），然后把剩下的点（下图红点）放在一边，再取出一对输入的点对（绿色点）：

然后将绿色点作为头和尾将剩余点或树根串联起来，如图：

这样保证了每条边都可以走到，更重要的是，它代码好写。

写代码时要注意的是：每次连边后都要记录上一次连边的点，下一次要用。

code

#include<bits/stdc++.h>
using namespace std;
#define N 300005
int n,m,f[N];
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int last,cnt=0;
struct node{
    int x,y;
}e[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y;
        if(find(e[i].x)!=find(e[i].y))f[find(e[i].y)]=find(e[i].x);
        else{
            cout<<"No"<<'\n';
            return 0;
        }
    }
    cout<<"Yes"<<'\n';
    for(int i=1;i<m;i++)cout<<e[i].x<<" "<<e[i].y<<'\n';
    last=e[m].x;
    for(int i=1;i<=n;i++){
        if(find(i)==i&&find(i)!=find(e[m].x)){
            cout<<last<<" "<<i<<'\n';
            last=i;
        }
    }
    cout<<e[m].y<<" "<<last<<'\n';
    return 0;
}