欧拉回路

欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。

程序实现一般是如下过程：

1.利用并查集判断图是否连通，即判断p[i] < 0的个数，如果大于1，说明不连通。

2.根据出度入度个数，判断是否满足要求。

3.利用dfs输出路径。

比较好的题目是poj2337，判断单词是否连成一排的。

poj2337

判断是否有欧拉路或者欧拉回路 DFS输出最小字典序路径以每个字母为顶点单词为边欧拉路只走一次边

先将单词按字典序由大到小排序因为建立邻接表的时候是逆序建立再判欧拉路和欧拉回路 DFS输出路径

View Code

  1 #include <iostream>
  2 #include<string.h>
  3 #include<cstdio>
  4 #include<algorithm>
  5 using namespace std;
  6 struct node
  7 {
  8     int v,next;
  9 }men[1000011];
 10 struct mode
 11 {
 12     char da[25];
 13 }s[10011];
 14 int first[10011],father[10011],str[10011],f[10011],n,t,o;
 15 int find(int x)
 16 {
 17     if(x!=father[x])
 18     father[x] = find(father[x]);
 19     return father[x];
 20 }
 21 void init()
 22 {
 23     t = 0;
 24     memset(first,-1,sizeof(first));
 25 }
 26 void add(int u,int v)
 27 {
 28     int i,x;
 29     men[t].v = v;
 30     men[t].next = first[u];
 31     first[u] = t;
 32     t++;
 33 }
 34 bool cmp(mode a,mode b)
 35 {
 36     return strcmp(a.da,b.da)>0;
 37 }
 38 void dfs(int x,int d)
 39 {
 40     int i,j,v;
 41     if(o)
 42     return ;
 43     str[d] = x;
 44     if(d==n)
 45     {
 46         o = 1;
 47         return;
 48     }
 49     for(i = first[x] ; i!=-1 ;i = men[i].next)
 50     {
 51         v = men[i].v;
 52         if(!f[v])
 53         {
 54             f[v] = 1;
 55             dfs(v,d+1);
 56             f[v] = 0;
 57         }
 58     }
 59 }
 60 int main()
 61 {
 62     int i,j,m,k,t,din[1011],dout[1011],x;
 63     char max[25];
 64     scanf("%d",&t);
 65     while(t--)
 66     {
 67         init();
 68         memset(din,0,sizeof(din));
 69         memset(dout,0,sizeof(dout));
 70         memset(f,0,sizeof(f));
 71         int flag = 1;
 72         o = 0;
 73         scanf("%d%*c",&n);
 74         for(i = 1; i <= n ; i++)
 75         father[i] = i;
 76         for(i = 1; i <= n ; i++)
 77         {
 78             scanf("%s",s[i].da);
 79             char u = s[i].da[0];
 80             char v = s[i].da[strlen(s[i].da)-1];
 81             dout[u-'a']++;
 82             din[v-'a']++;
 83         }
 84         sort(s+1,s+n+1,cmp);
 85         for(i = 1;i <= n ; i++)
 86         {
 87             k = strlen(s[i].da);
 88             for(j = 1; j <= n ; j++)
 89             if(j!=i&&s[i].da[k-1]==s[j].da[0])
 90             {
 91                 int px = find(i);
 92                 int py = find(j);
 93                 if(px!=py)
 94                 father[px] = py;
 95                 add(i,j);
 96             }
 97         }
 98         int w = 0;
 99         for(i = 1; i <= n ; i++)
100         if(find(i)==i)
101         {
102            w++;
103         }
104         if(w>1)
105         {
106             printf("***\n");
107             continue;
108         }
109         int f1 = 0,f2 = 0;
110         flag = 1;
111         for(i = 0; i < 26 ; i++)
112         {
113             if(din[i]!=dout[i])
114             {
115                 if(dout[i]-din[i]==1)
116                 {
117                     f1++;
118                     x = i;
119                 }
120                 else
121                 if(din[i]-dout[i]==1)
122                 f2++;
123                 else
124                 {
125                     flag = 0;
126                     break;
127                 }
128             }
129             if(f1>1||f2>1)
130             {
131                 flag = 0;
132                 break;
133             }
134         }
135         if(!flag)
136         {
137             printf("***\n");
138            continue;
139         }
140         if(f1==0&&f2==0)
141         {
142             f[n] = 1;
143             dfs(n,1);
144         }
145         else
146         for(i = n ; i >= 1; i--)
147         {
148             if(s[i].da[0]==x+'a')
149             {
150                 f[i] = 1;
151                 dfs(i,1);
152                 f[i] = 0;
153             }
154             if(o)
155             break;
156         }
157         for(i = 1 ;i < n ; i++)
158         printf("%s.",s[str[i]].da);
159         printf("%s\n",s[str[n]].da);
160     }
161     return 0;
162 }