这个很简单但挺实用，大家应该对于dfs都很熟悉了，毕竟已经学了图论，不多赘述 。
（弗勒里）算法
重点！！！
说句实话，算法就是加上割边判定的深搜 。
虽然复杂度较差，但实现简单 。（所以有什么用）
这个算法是较为高效地运用了图论思想，也是求解欧拉回路最有名且使用广泛的算法之一 。
这个算法是弗勒里(B.H.) 在1883 年给出了在欧拉图中找出一个欧拉环游的多项式时间算法 。
运用前我们需要明确“桥”（割边）的含义 。
假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边 。
然后看算法 。
其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边 。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完 。遵循这样一个原则就可以找出图的一个欧拉回路来 。
我下面虽然有实现模板，但我把重点截出来一下 。
核心代码挺简单的，主要是对于割边的判断很重要 。
查并集+递归
并查集一般用来确定图是否连通，然后根据度来判断是否存在欧拉图，递归用来输出路路径 。
但递归打印路径时候需要注意：必须先确定里面有欧拉路径，欧拉回路直接打印即可，欧拉通路需要找到起点 。
有部分题需要用到这一种算法，但是实现真的挺复杂的 。
另外，这玩意儿容易爆栈 。
毕竟递归次数有点多 。
所以防止爆栈的话用非递归 。
这个方法挺迷，参考大佬的博客：dalao传送门
这一部分仅供参考，最好自己实现算法，毕竟欧拉图深搜挺简单的 。
选了可读性稍微好一点的模板，主要大部分博客上的代码写得真的很乱，可读性差 。前两个模板来自楼上提到的大佬 。
1、查并集判断连通图
#include #include #define N 1000using namespace std;int n, m;int f[N],degree[N];//记录第i点的度数void init(){for (int i = 1; i <= n; i++)f[i] = i;}int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}void merge(int x, int y){int t1, t2;t1 = find(x); t2 = find(y);if (t1 != t2) f[t2] = t1;else return;}int isEuler(){int cnt=0;for (int i = 1; i <= n; i++){if (degree[i] & 1) cnt++;if(cnt>2) return 0;}if(cnt==2||cnt==0) return 1;///cnt==2 欧拉通路 cnt==0欧拉回路return 0;}int isconnect(){int cnt = 0;int ff=find_(1);for (int i=2; i <= n; i++){if (find_(i)!=ff)return 0;}return 1;}int main(){while (scanf("%d", &n) != EOF && n){init();memset(degree, 0, sizeof(degree));scanf("%d", &m);int t1, t2;for (int i = 0; i < m; i++){scanf("%d%d", &t1, &t2);//输入有t1，t2相等的情况if (t1 == t2)continue;degree[t1]++; degree[t2]++;merge(t1, t2);}printf("%d\n", isEuler() && isconnect());}return 0;}
2、输出路径
#include#include#include#include#include#include#include#include#include#define ll long long#define PI 3.1415926535897932384626#define inf 0x3f3f3f3fusing namespace std;const int maxn=6000;struct Edge{int to,next,id;bool flag;}edge[maxn];int head[maxn];int in[maxn];int tot;void addedge(int u,int v,int w){edge[tot].to=v;edge[tot].next=head[u];edge[tot].id=w;edge[tot].flag=false;head[u]=tot++;}int start;vectorans;void init(){tot=0;memset(head,-1,sizeof(head));memset(in,0,sizeof(in));}void dfs(int x){for(int i=head[x];i!=-1;i=edge[i].next){if(!edge[i].flag){edge[i].flag=true;edge[i^1].flag=true;dfs(edge[i].to);ans.push_back(i);//记录边的号码}}}int main(){int x,y,c;while(scanf("%d%d",&x,&y)){if(x==0&&y==0)break;init();scanf("%d",&c);addedge(x,y,c);addedge(y,x,c);in[x]++;in[y]++;start=min(x,y);while(scanf("%d%d",&x,&y)){if(x==0&&y==0)break;scanf("%d",&c);addedge(x,y,c);addedge(y,x,c);in[x]++;in[y]++;}int flag=1;for(int i=1;i