fleury算法求欧拉路径(欧拉回路)模板

首先简单讲一下思想 首先先判断这个无向图存在欧拉路径(其实欧拉回路也很容易判)

把每个点连接的边数存下来 如果只有两个或者没有点有奇数条边与它相连 那么就存在欧拉路径

然后从一个奇数点开始(如果没有奇数点就任意一个点)随便选一个点开始进行深搜 把经过的每一个点存到栈里面 把经过的边删掉 

然后在栈里面的点如果还有边与它相连 又继续深搜 否则就把这个点弹出去 输出

这样时间复杂度为 O(m)

用矩阵存的 比较LOW不要骂我。。。(反正欧拉回路也是水题……)

代码如下

#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
stack<int>st;
int mp[110][110],n,m;//n为点数 m为边数
int num[110],sum,start;
void dfs(int x)
{
	st.push(x);
	for(int i=0;i<=n;i++)
	{
		if(mp[x][i])
		{
			mp[x][i]--;
			mp[i][x]--;
			dfs(i);
			break;
		}
	}
	return;
}
void fleury(int x)
{
	st.push(x);
	while(!st.empty())
	{
		int p=st.top();
		int flag=0;
		for(int i=0;i<=n;i++)
			if(mp[p][i])
			{
				flag=1;
				break;
			}
		if(flag)
		{
			st.pop();
			dfs(p);
		}
		else
		{
			st.pop();
			printf("%d\n",p);
		}
	}
	return;
}
int main()
{
	int x,y;
	while(~scanf("%d%d",&n,&m))
	{
		sum=0;
		memset(num,0,sizeof(num));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			mp[x][y]++;
			mp[y][x]++;
			num[x]++;num[y]++;
		}
		start=x;
		for(int i=0;i<=n;i++)
			if(num[i]&1)
			{
				start=i;
				sum++;
			}
		if(sum==0||sum==2)fleury(start);
		else printf("No solution\n");
	}
	return 0;
}