P10179题解

· · 题解

这道题是一道构造题。

我们考虑每一个事件都直接连边，发现为了让以后找到的方案仍能合法，可以设置一个种图，形如 c_0\implies x_c,x_c\implies c_1,x\implies c_2\dots x\implies c_k，其中 x_c 表示用于 c 中的一个不确定的点，可以看出这个图中任意两个确定的点距离为 2。

因此 c 的顺序不重要，而有解当且仅当存在 x\not\in c。

由于顺序不重要并且 c 中任意两点都合法，因此可以把 c 看做一个集合。

那么我们可以通过并查集实现。

接着考虑 x_c，以及合并这些集合，显然可以在并查集后将时间全部处理后再次合并，并且仍然合法。

如果只剩一个集合，可以发现无法构造出 x，此时无解。

接着考虑两个集合，设第二个集合为 d，由于互不影响，因此可以使 x_c=d_0,x_d=c_0，该答案合法，即为解（此处其它构造方式也行，但这个方法做着认为会更好实现一些）。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int f[1000009];
int getfa(int t){
    if(f[t]==t){
        return t;
    }
    return f[t]=getfa(f[t]);//此处压缩路径有大用
}
void merge(int u,int v){
    f[getfa(u)]=getfa(v);
}
void _main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){//初始化，如果 memset 可能会超时
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        merge(u,v);//并查集
    }
    int z;
    z=0;
    for(int i=1;i<=n;i++){
        getfa(i);//使得通过压缩路径让 f[i] 直接表示并查集中的根节点，可以不写，但后面的 f[x] 就要替换为 getfa(x)，
    }//我们将 f[i] 设为包含 i 的集合中编号为 0 的节点
    for(int i=1;i<=n;i++){
        if(f[i]!=f[n]){//f[n] 为其中一个集合的 0 号节点，寻找其它集合以求是否有解以及下一步操作
            z=f[i];//z 为某另一个集合的 0 号节点
            break;
        }
    }
    if(!z){//都是在一个集合，无法构造 x 无解
        cout<<"No"<<endl;
        return;
    }
    for(int i=1;i<n;i++){//将多余集合合并
        if(f[i]!=f[n]){
            merge(z,i);
        }
    }
    for(int i=1;i<=n;i++)
        getfa(i);
    z=f[z];//d[0]=f[z],c[0]=f[n]
    cout<<"Yes"<<endl;
    cout<<f[z]<<" "<<f[n]<<endl;
    for(int i=1;i<=n;i++){//输出答案
        if(i!=z&&i!=f[n]){
            if(f[i]==z){
                cout<<i<<" "<<f[n]<<endl;
            }else{
                cout<<i<<" "<<z<<endl;
            }
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        _main();//面对多组测试数据的好方法
    }
    return 0;
}