欧拉回路（附模板）

C++模版：

// 求欧拉回路或欧拉路，邻接阵形式，复杂度o（n^2）
//返回路径长度，path返回路径(有向图是得到的是反向路径)
//传入图的大小n和邻接阵mat，不相交邻点边权0
//可以有自环与重边，分为无向图和有向图
#define MAXN 100 


void find_path_u(int n,int mat[][MAXN],int now,int& step,int* path)
{
　　int i; 
　　for (i=n-1;i>=0;i--) 
　　　　while (mat[now][i])
　　　　{ 
   　　 mat[now][i]--,mat[i][now]--; 
   　　 find_path_u(n,mat,i,step,path); 
　　　　} 
　　path[step++]=now; 
}


void find_path_d(int n,int mat[][MAXN],int now,int& step,int* path)
{ 
　　int i; 
　　for (i=n-1;i>=0;i--) 
　　　　while (mat[now][i])
　　　　{ 
   　　 mat[now][i]--; 
   　　 find_path_d(n,mat,i,step,path); 
　　　　} 
　　path[step++]=now; 
}


int euclid_path(int n,int mat[][MAXN],int start,int* path)
{ 
　　int ret=0; 
　　find_path_u(n,mat,start,ret,path); 
　　// find_path_d(n,mat,start,ret,path); 
　　return ret; 
}

练习题：
　　
1 HDU 3018 Ant Trip
   一笔画问题，无向图欧拉路或者欧拉回路，注意题目说了，如果是孤立点，则不用考虑。
  
2 POJ 1041 John's trip
 
3 POJ 1386 Play on Words
   　貌似很经典的模型了，应该叫 单词接龙吧。
   　本题要求判断是否有 有向图欧拉路
 
4 POJ 2230 Watch Cow
    　题目描述每条路必须走两次，且方向不同，其实一样了，有向图的欧拉回路
不过需要输出的是路径中的节点。

5 POJ 2513 Colored Sticks
   　比较简单，判定是否存在 无向图欧拉路
 
6 POJ 2337 Catenyms
      还是单词 首尾相连，要求判断，然后输出字典序最小的
   　
7 POJ 1392 Ouroboros Snake
http://blog.csdn.net/yueashuxia/archive/2010/07/12/5729878.aspx
   　这里涉及到DeBruijin图
   　本题要求 按顺序输出 组成的数字。
8 HDU 2894 DeBruijin
　　同上，这次要输出串