准确说应该是无向图的欧拉回路
应该满足的条件是每个点的度是偶数
这个提要求输出字典序最小的方案，为什么SPJ呢？？
因为题目允许我们从任意一个点开始走，我们只要输出从任意一点出发的欧拉回路方案即可~
是一道欧拉回路模板题~
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 #define M 20000 6 #define N 100 7 using namespace std; 8 int map[N][M],stack[M],p,d[N],maxn,maxm; 9 bool vis[M]; 10 void dfs(int u) 11 { 12 for(int i=1;i<=maxm;i++) 13 if(map[u][i]&&!vis[i]) 14 { 15 vis[i]=true; 16 dfs(map[u][i]); 17 stack[++p]=i; 18 } 19 } 20 void prt() 21 { 22 while(p) 23 { 24 printf("%d ",stack[p]); 25 p--; 26 } 27 printf("\n"); 28 } 29 void go() 30 { 31 for(int i=1;i<=maxn;i++) 32 if(d[i]&1) 33 { 34 printf("Round trip does not exist.\n"); 35 return; 36 } 37 memset(vis,0,sizeof vis); 38 p=0; 39 dfs(maxn); 40 prt(); 41 } 42 int main() 43 { 44 int x,y,z; 45 while(scanf("%d%d",&x,&y),x||y) 46 { 47 memset(map,0,sizeof map); 48 memset(d,0,sizeof d); 49 maxn=0; maxm=1; 50 scanf("%d",&z); 51 map[x][z]=y; map[y][z]=x; 52 d[x]++; d[y]++; 53 maxn=max(maxn,max(x,y)); 54 maxm++; 55 while(scanf("%d%d",&x,&y),x||y) 56 { 57 scanf("%d",&z); 58 map[x][z]=y; map[y][z]=x; 59 d[x]++; d[y]++; 60 maxn=max(maxn,max(x,y)); 61 maxm++; 62 } 63 go(); 64 } 65 system("pause"); 66 return 0; 67 }