CF325E 题解

· · 题解

CF325E 题解

Problem Link

题目大意

给一张 n 个点的图，编号 0\sim n-1，连边 i\to 2i\bmod n,i\to (2i+1)\bmod n，求一条哈密尔顿回路。

数据范围：n\le 10^5。

思路分析

首先 n\bmod 2=1 一定不行，此时 0 的入点为 0,\dfrac{n-1}2，n-1 的入点为 n-1,\dfrac{n-1}2，显然矛盾。

因此 n\bmod 2=0，注意到 i,i+\dfrac n2 的出边都是连向 2i,2i+1 的，因此每个 i,i+\dfrac n2 只有两种连法，任取一种一定形成若干个环。

若所有 i,i+\dfrac n2 在一个环上，那么可以证明所有点都在一个环上。因此对于每一对不连通的 i,i+\dfrac n2，交换他们的出边使两个环连通即可。

时间复杂度 \mathcal O(n\alpha (n))。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int dsu[MAXN],nxt[MAXN];
inline int find(int x) { while(x^dsu[x]) x=dsu[x]=dsu[dsu[x]]; return x; }
inline void merge(int x,int y) { dsu[find(x)]=find(y); }
signed main() {
    int n;
    scanf("%d",&n),iota(dsu,dsu+n,0);
    if(n&1) return puts("-1"),0;
    for(int i=0;i<n/2;++i) merge(i,nxt[i]=i*2),merge(i+n/2,nxt[i+n/2]=i*2+1);
    for(int i=0;i<n/2;++i) if(find(i)^find(i+n/2)) swap(nxt[i],nxt[i+n/2]),merge(i,i+n/2);
    printf("0 "); for(int i=nxt[0];i;i=nxt[i]) printf("%d ",i); puts("0");
    return 0;
}