从无向图中的一个结点出发走出一条道路，每条边恰好经过一次。这样的路线称为欧拉道路。

奇点的概念：一个点的度数为奇数的时候，这个点就称为：奇点。

无向图中结论：

不难发现，在欧拉道路中，除了起点跟终点，其他所有点的度数都应该是偶数！

如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉道路。

如果有两个奇点，则必须从其中一个出发，然后从另外一个终止。

如果不存在奇点，则可以从任意点出发，最终一定会回到原点（这样的欧拉道路又称为欧拉回路）。

有向图中结论：

前提：在忽略边的方向后，图必须是连通的。

最多只能有两个点为奇点，而且必须是其中一个点的出度恰好比入度大一（这个点用来作为起点）；另外一个入度比出度大一（这个点用来作为终点）。

#include <iostream>#include <string>#include <stack>#define MAXN 1000using namespace std;int G[MAXN][MAXN], vis[MAXN][MAXN];stack<string> s;int n, m;void dfs(int u){	for(int v = 0; v < n; ++v) if(G[u][v] && !vis[u][v]){		vis[u][v] = vis[v][u] = 1; 		//vis[u][v] = 1; 有向图		dfs(v);		string a(1, u+'0');		string b(1, v+'0');		string str(a + "->" + b);		s.push(str);			}}int main(){	cin >> n >> m;	memset(G, 0, sizeof(G));	memset(vis, 0, sizeof(vis));	for(int i = 0; i < m; ++i){		int u, v;		cin >> u >> v;		G[u][v] = G[v][u] = 1;//无向图		//G[u][v] = 1; 有向图	}	dfs(0);	while(!s.empty()){		cout << s.top() << endl;		s.pop();	}	return 0;}