题解：P15057 [UOI 2023 II Stage] Roads of Potokolandiya

__Wanna__Accepted__ · 2026-01-26 14:03:16 · 题解

不要推数学规律了，直接上并查集得了。

题解

题目等价于一个 n 个点 n 条边的无向图，判断其连通块数是否为 1。

那我们直接用并查集维护，然后统计 f_i=i 的数量即连通块的数量。

题目还要求输出两个属于不同连通块的点，那我们记录两个然后输出。

代码

#include<iostream>
using namespace std;
int n,x,y,f[1000001];
int find(int x){
    return (f[x]==x)?x:(f[x]=find(f[x]));
}
int main(){
    cin>>n;
    for(int i=n;i;i--)f[i]=i;
    for(int i=n;i;i--)f[find(i)]=find((i+i>n)?(i+i-n):(i+i));
    for(int i=n;i;i--)
        if(f[i]==i)x?(y=i):(x=i);
    if(y)cout<<"NO\n"<<x<<' '<<y;
    else cout<<"YES";
}