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

· · 题解

前言

暴力过了？

题意

图中连 i 和 (i+i)\bmod n 两点，求图是否只有一个联通块。

解题思路

求联通块，考虑暴力并查集。连 i 和 (i+i)\bmod n 两点，判是否只有一个联通块即可。

当无解时，输出 1,n 即可（我不会证，交给其他题解了）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void join(int x,int y){
    int f1=find(x),f2=find(y);
    if(f1==f2)return;
    fa[f1]=f2;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)join(i,(i+i)>n?i+i-n:i+i);
    int cnt=0;
    for(int i=1;i<=n;i++){if(i==fa[i])cnt++;if(cnt>1){printf("NO\n");printf("%d %d",1,n);return 0;}}
    printf("YES");
    return 0;
}