ssoj2434: Sleet（欧拉回路）

ssoj2434: Sleet（欧拉回路）

题意：男女比例达到了惊人的1:1，n个男生和n个女生，男生编号为0,2,4,…2n-2，女生编号为1,3,5,…2n-1，他们按照编号坐成一圈，Capo的老师有个要求，编号为x的顺时针方向下一个人编号必须是2x,2x+1,2x-2n,2x+1-2n中的一个。想让你设计坐座位的方案。

思路：每个点的出度（连到2x%2n & (2x+1)%2n）和入度都为2，且只能经过一次。即哈密顿回路。再转换成欧拉回路，个人理解，把点转化成边，结点根据需要加入。即：n=4来说，边0（先接到点0）要接到边0和边1，边1（接到点1）要接到边2和边3，边2（接点2）要接到边4和边5，边3（接点3）要接到边6和边7，边4（接点0）要接到边0和边1，边5（接点1）要接到边2和边3，边6（接点2）要接到边4和边5，边7（接点3）要接到边6和边5。即点i（0~n-1）要接到（2i+1）%n & 2i%n 两点，且边的编号为2i+1 & 2i。求欧拉回路。

贴代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000666;
struct data{int u,v,num,nxt;
}e[maxn];
int n,m,cnt,fst[maxn],a[maxn],t;
bool f[maxn];
inline void add(int x,int y,int z){e[++cnt].u=x;e[cnt].v=y;e[cnt].num=z;e[cnt].nxt=fst[x];fst[x]=cnt;
}
inline void dfs(int x){for(int i=fst[x];i;i=e[i].nxt){if(!f[e[i].num]){f[e[i].num]=1;dfs(e[i].v);a[++t]=e[i].num;}}
}
int main(){while(scanf("%d",&n)!=EOF){t=0;cnt=0;memset(f,0,sizeof(f));memset(fst,0,sizeof(fst));for(int i=0;i<n;++i){add(i,(2*i)%n,2*i);add(i,(2*i+1)%n,2*i+1);}dfs(0);while(t)printf("%d ",a[t--]);printf("n");}return 0;
}