欧拉回路总结

1. 欧拉路径定义：

     图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。

2.2. 欧拉路径判定（是否存在）：

     有向图欧拉路径：图中恰好存在 1 个点出度比入度多 1（这个点即为 起点 S），1 个点入度比出度多 1（这个点即为 终点 T），其余节点出度=入度。

     有向图欧拉回路：所有点的入度=出度（起点 S 和终点 T 可以为任意点）。

     无向图欧拉路径：图中恰好存在 2 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 S 和 终点 T。

     无向图欧拉回路：所有点的度数都是偶数（起点 S 和终点 T 可以为任意点）

注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。

有向图找欧拉路径（字典序最小）:

//使用邻接表
//有可能没有欧拉路径的情况
#includeusing namespace std;
const int N=100005;
int n,m;
vectormp[N],ans;
int du[N][2];
int s=1;
int del[N];
queueq;
void dfs(int i)
{
	for(int j=del[i];j>n>>m;
	for(int i=0;i>a>>b;
		mp[a].push_back(b);
		du[a][0]++;//入度
		du[b][1]++;//出度
	}
	for(int i=1;i=1;i--)
	{
		if(du[i][0]!=du[i][1])
		{
			flag=false;
			if(du[i][0]-du[i][1]==1)
			{
				num[0]++;
				s=i;
			}
			else if(du[i][1]-du[i][0]==1)
			{
				num[1]++;
			}
			else
			{
				cout<<"No";
				return 0;
			}
		}
	}
	if(!flag&&!(num[0]==num[1]&&num[0]!=0))
	{
		//cout<<num[0]<<' '<<num[1];
		cout<=0;i--)
	{
		cout<<ans[i]<<' ';
	}
	return 0;
}

无向图找欧拉路径（字典序最小）:

//邻接矩阵
//保证有欧拉路径的情况
#includeusing namespace std;
const int N=100005;
int n,m;
vectorans;
int du[N];
int mp[505][505];
int f[505];
int s=501;
queueq;
void dfs(int i)
{
	for(int j=1;j0)
		{
			mp[i][j]--;
			mp[j][i]--;
			dfs(j);
		}
	}
	ans.push_back(i);
}
int main()
{
	
	cin>>n;
	for(int i=0;i>a>>b;
		mp[a][b]++;
		mp[b][a]++;
		du[a]++;//度
		du[b]++;
		s=min(s,a);
		s=min(s,b);
	}
	bool flag=true;
	int num;
	for(int i=1;i=0;i--)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}