欧拉路径：在一个图中，从i点出发，能将每个边遍历一次最终达到j点的一条路径

欧拉回路：i=j时的欧拉路径

无向图

欧拉回路：在无向图中，只要每个点的度数均为偶数，那么必定存在欧拉回路。因为每个点的度是偶数，意味着总有成对的入边和出边，则不会出现卡在一个节点的情况。

欧拉路径：有且仅有两个点的度数为奇数，那么存在从其中一个点到另一个点的欧拉路径。

有向图

欧拉回路：所有点的入度等于出度，就存在一条欧拉回路。类似于无向图，每个节点都有成对的入边和出边，那么必定存在欧拉回路

欧拉路径：至多一个点的出度 = 入度 + 1 (起点) ， 之多一个点的 入度 = 出度 + 1 （终点） 。

至此判断一个图是否存在欧拉回路和欧拉路径已经可以完成。
接下来是知道存在的条件下找出路径。也就是常规的dfs把每条边走一遍。但是注意，第一个栈底的是无路可走的节点，我们在按照栈输出就行，也就是逆序输出，原因如下：

例如 1 - > 2 -> (3 -> 2 ) -> 1 这是个存在环的回路， 但是也满足欧拉路径的要求。
我们在dfs时可以看做每条边都有概率执行， 因此我们会得到这个dfs序: 1 -> 2 -> 1 （然后回溯返回到2） -> 3 - > 2。 顺序输出的话，把一些行不通的路径也输出了 。逆序输出则保证了栈底的必须是第一个无路可走的节点，也就是终点。

// 有可能两个点之间存在多条边，那么可以用vis[x][i] -- ，减一次走一次
void dfs(int x)
{
 for(int i=0; i v);//存储路径上的边
cnt++;
  }
 }

 ans.push(x);//存储路径上的点
}

应用：

1、Uva 10054 The Necklace

题意：给你n个珠子，一个珠子分为两半有两种颜色，用1到50来表示50种不同的颜色。把这些珠子串起来，两个紧挨着的珠子要满足一个条件就是接触的那部分颜色要相同

例如(1,2)(2,4)，两个珠子的接触部分颜色相同都为2。当然，因为珠子最后是连成环的，第一个珠子和最后一个珠子也会接触，也要买满足这个条件

先输入T，有T组数据

输入n，有n个珠子

下面n行每行两个数字表示这个珠子的两个颜色，然后问你能不能连成一条链，能的话输出任意一种连接情况即可，不能的话输出失败.

思路：

给定的珠子上的两个颜色，看出无向图两个点连上一条边。题目转化成无向图的欧拉回路是否存在，存在即输出。

代码：

#include 
#include 

using namespace std;

vectorG[100];
int vis[100][100];
int d[100];
void dfs(int x)
{
 for(int i=0; i0)
  {
vis[x][v]--;
vis[v][x]--;
dfs(G[x][i]);
printf("%d %d\n",v,x);

  }
 }

}

int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 while(m--)
 {
  int a,b;
  cin>>a>>b;
  G[a].push_back(b);
  d[a]++;
  d[b]++;
  vis[a][b] ++;
  vis[b][a] ++;
 }
 for(int i=1; i<=n; i++)
  if(d[i]%2)
  {
puts("some beads may be lost\n");
return 0;
  }

 dfs(1);

 return 0;
}