2019 ICPC Asia Xuzhou Regional J. Loli, Yen-Jen, and a graph problem(欧拉回路+构造)

题目

输入一个n(n<=1e3)，代表n个点的完全无向图，

你需要输出n-1行，分别代表长度为1,2，...，n-1的链上经过的点，

使得每条链在原图中都是连续的，且任意两条链之间没有交边

思路来源

题解

①n是奇数，欧拉回路，注意弧优化

②n是偶数，考虑长为n-2和n-1的两条链如何构造，

令a=n-1，b=n，使a和b交替穿插在[1,n-2]个点里，并最后回到b，

最终构成a-1-b-2-...-b-(n-2)-a-b的一个长为2*n-3的链，然后拆成n-2和n-1的两条链

然后删掉a和b两个点，递归解决n-2的子问题即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<set>
using namespace std;
#define pb push_back
typedef pair<int,int> P;
const int N=1e3+10,M=1e6+10;
vector<P>e[N];
bool vis[M],used[N];
int now[N],ans[M],cnt,c;
int op,n,m,u,v;
void dfs(int u){used[u]=1;while(now[u]<e[u].size()){int v=e[u][now[u]].first,id=e[u][now[u]].second,fid=abs(id);now[u]++;if(vis[fid])continue;vis[fid]=1;dfs(v);ans[++cnt]=v;}
}
void odd(int n){for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){e[i].pb(P(j,++c));e[j].pb(P(i,c));}}dfs(1);ans[++cnt]=1;//后序回到1 int l=1;for(int len=1;len<n;len++){int r=l+len;for(int k=l;k<=r;++k){printf("%d%c",ans[k]," \n"[k==r]);}l=r;}
}
void even(int n){if(n==2){puts("1 2");return; }even(n-2);vector<int>ans;int a=n-1,b=n;for(int i=1;i<=n-2;i+=2){ans.pb(a);ans.pb(i);ans.pb(b);ans.pb(i+1);}ans.pb(a);ans.pb(b);int sz=ans.size(),mid=sz/2-1; for(int i=0;i<=mid;++i){printf("%d%c",ans[i]," \n"[i==mid]);}for(int i=mid;i<=sz-1;++i){printf("%d%c",ans[i]," \n"[i==sz-1]);}
}
int main(){scanf("%d",&n);n&1?odd(n):even(n);return 0;
}