uva 10054 The Necklac（欧拉回路）

明显的欧拉回路，把颜色作为点，建图后，做一遍欧拉回路。不过我是现学的，打印路径上纠结了一下，发现随着FindEuler（）的递归调用的结束，不断把点压入栈中，从后向前打印，遇到"支路"会先处理好支路再继续的。这样就可以顺序打印路径了。如果是直接打印或放在队列里，会发现打印出来的项链的关系正好相反，即前一行的第一个与本行的第二个颜色相同。

邻接表又开小了，MAXN<<1 。还有就是用STL的栈TLE了，还是手写吧= =

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stack>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const int MAXN=55;
  8 const int MAXM=1111;
  9 
 10 int sta[MAXM][2],top;
 11 
 12 struct Edge{
 13     int v,next;
 14     int vis;
 15     Edge(){}
 16     Edge(int _v,int _next):v(_v),next(_next),vis(0){}
 17 }edge[MAXM<<1];
 18 
 19 int tol,head[MAXN],E;
 20 int degree[MAXN];
 21 
 22 void init()
 23 {
 24     tol=0;E=0;
 25     memset(head,-1,sizeof(head));
 26     memset(degree,0,sizeof(degree));
 27 }
 28 
 29 void add(int u,int v)
 30 {
 31     edge[tol]=Edge(v,head[u]);
 32     head[u]=tol++;
 33 }
 34 
 35 int FindVertex(){
 36     for(int i=1;i<=50;i++)
 37     {
 38         if(degree[i])
 39             return i;
 40     }
 41     return -1;
 42 }
 43 
 44 void FindEuler(int u)
 45 {
 46     for(int i=head[u];i!=-1;i=edge[i].next)
 47     {
 48         int v=edge[i].v;
 49         if(!edge[i].vis){
 50             edge[i].vis=edge[i^1].vis=1;
 51 
 52             FindEuler(v);
 53             sta[top][0]=u;
 54             sta[top++][1]=v;
 55         }
 56     }
 57 }
 58 
 59 bool EulerCircuit()
 60 {
 61     for(int i=0;i<=50;i++)
 62         if(degree[i]%2!=0)
 63             return false;
 64     int s=FindVertex();
 65     if(s==-1)
 66         return false;
 67 
 68     top=0;
 69     FindEuler(s);
 70 
 71     if(top!=E)
 72         return false;
 73     return true;
 74 
 75 }
 76 
 77 int main()
 78 {
 79     int T,k,n;
 80     int a,b;
 81     scanf("%d",&T);
 82     for(k=1;k<=T;k++)
 83     {
 84         scanf("%d",&n);
 85 
 86         init();
 87         for(int i=0;i<n;i++)
 88         {
 89             scanf("%d%d",&a,&b);
 90             add(a,b);
 91             add(b,a);
 92             E++;
 93             degree[a]++;
 94             degree[b]++;
 95         }
 96 
 97         if(k!=1)
 98             puts("");
 99         printf("Case #%d
",k);
100         if(EulerCircuit()){
101             while(top!=0){
102                 top--;
103                 printf("%d %d
",sta[top][0],sta[top][1]);
104             }
105         }else
106             printf("some beads may be lost
");
107     }
108     return 0;
109 }

View Code

补充：用邻接表打印字典序最小的回路，应该在建图后对每个adjacency list 排序。

如果在有向图上做欧拉回路，只需把判断偶点改为出入度相等即可。

Euler Trail与Euler Circuit 最多相差一条边（回路本身也是一条迹），所以把判断偶点改为恰有两个奇点或没有奇点即可。