题目
输入一个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;
}
