1、定义：
欧拉通路(回路)：通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的
通路(回路)称为欧拉通路(回路)。
欧拉图与半欧拉图：具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的
图称为半欧拉图。
桥：设无向图G=<V,E>，若存在边集E的一个非空子集E1，使得p(G-E1)>p(G)，而对
于E1的任意真子集E2，均有p(G-E2)=p(G)，则称E1是G的边割集，或简称割集；
若E1是单元集，即E1={e}，则称e为割边或桥。[p(G)表示图G的连通分支数.]
2、定理：
<无向图>
定理1：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。
定理2：无向图G是半欧拉图当且仅当G是连通图，且G中恰有两个奇度顶点。
<有向图>
定理1：有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。
定理2：有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其
中一个入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于
出度。
3、求欧拉回路的Fleury算法：
设G为欧拉图，一般说来G中存在若干条欧拉回路，下面是求欧拉回路的Fleury算法：
Fleury算法：
（1）任取v0∈V(G)，令P0=v0；
（2）设Pi=v0e1v1e2...eivi已经行遍，按下面方法来从E(G)-{e1,e2,...,ei}中选
取ei+1：
（a）ei+1与vi想关联；
（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,...,ei}中的桥.
（3）当（2）不能再进行时，算法停止。
可以证明，当算法停止时所得简单回路Pm=v0e1v1e2...emvm（vm=v0）为G中的一条欧拉回路。
View Code
// I'm the Topcoder //C #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #include <time.h> //C++ #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <cctype> #include <stack> #include <string> #include <list> #include <queue> #include <map> #include <vector> #include <deque> #include <set> using namespace std; //*************************OUTPUT************************* #ifdef WIN32 #define INT64 "%I64d" #define UINT64 "%I64u" #else #define INT64 "%lld" #define UINT64 "%llu" #endif //**************************CONSTANT*********************** #define INF 0x3f3f3f3f #define eps 1e-8 #define PI acos(-1.) #define PI2 asin (1.); typedef long long LL; //typedef __int64 LL; //codeforces typedef unsigned int ui; typedef unsigned long long ui64; #define MP make_pair typedef vector<int> VI; typedef pair<int, int> PII; #define pb push_back #define mp make_pair //***************************SENTENCE************************ #define CL(a,b) memset (a, b, sizeof (a)) #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b)) #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c)) //****************************FUNCTION************************ template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); } template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; } template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; } // aply for the memory of the stack //#pragma comment (linker, "/STACK:1024000000,1024000000") //end const int maxn = 2000+10; struct stack{ int top; int node[maxn]; }s; int edges[maxn][maxn];//顶点的栈结构 int n,m;//顶点个数,边数 void dfs(int x){ s.top++; s.node[s.top]=x;//x入栈 for(int i=0;i<n;i++){ if(edges[i][x]>0){//存在边 edges[i][x]=0 ; edges[x][i]=0;//删除此边 dfs(i);//继续深搜 break; } } } void fleury(int x){//fleury算法 int b; s.top=0; s.node[s.top]=x;//入栈 while(s.top>=0){//栈不空 b=0;//判断点是否可以继续扩展 for(int i=0;i<n;i++){ if(edges[s.node[s.top]][i]>0){//存在边就是可以扩展 b=1; break; } } if(b==0) {//如果没有点可以扩展，输出并出栈 printf("%d ",s.node[s.top]+1);//因为输入的时候自己处理时顶点--了，所以这里+1 s.top--;//栈顶指针往下移动一格 } else { s.top--;//关键不可少 //printf("s.top=%d\n",s.top); //printf("s.node[s.top+1]=%d\n",s.node[s.top+1]); dfs(s.node[s.top+1]);//如果有就dfs,继续扩展 } } } int main(){ int s,t;//读入边的起点和终点 int degree,num,start;//每个顶点的度，奇度顶点的个数，欧拉回路的起点 while(scanf("%d%d",&n,&m)!=EOF){//顶点个数，边数 memset(edges,0,sizeof(edges)); for(int i=0;i<m;i++){ scanf("%d%d",&s,&t); edges[s-1][t-1]=edges[t-1][s-1]=1; } //如果存在奇度顶点，则从奇度顶点出发，否则从顶点0出发 num=0; start=0;//奇度顶点的个数,欧拉回路的起点 for(int i=0;i<n;i++){//计算每个顶点的度数（出度+入度） degree=0; for(int j=0;j<n;j++){ degree+=edges[i][j]; } if(degree%2==1){ start=i; num++; } } if(num==0||num==2) {fleury(start);} else { printf("NO Eular path\n"); } } return 0; } //input //9 14 //1 2 //1 8 //2 3 //2 8 //2 9 //3 4 //4 5 //4 6 //4 9 //5 6 //6 7 //6 9 //7 8 //8 9 //output //1 8 9 6 7 8 2 9 4 6 5 4 3 2 1 //result ok