欧拉路径回顾

xishanmeigao / 2023-08-25 / 原文

最近打模拟赛发现这东西忘得差不多了，赶紧补一下

Part 1：知识点

定义

经过图中所有边恰好一次的路径叫作欧拉路径
如果欧拉路径的起点和终点相同，则称其为欧拉回路

判定

有向图欧拉路径：图中恰好存在一个点的出度比入度多 \(1\)（起点 \(S\)），恰好存在一个点的入度比出度多 \(1\)（终点 \(T\)），其它点入度=出度
有向图欧拉回路：图中所有点的入度=出度
无向图欧拉路径：图中恰好存在两个点的度数为奇数（起点 \(S\) 和终点 \(T\)），其它点的度数均为偶数
无向图欧拉回路：图中所有点的度数均为偶数

\(\rm PS\)：存在欧拉回路则一定存在欧拉路径

Part 2：一些习题

P7771 【模板】欧拉路径

#include<bits/stdc++.h>
using namespace std;

const int N=1000010;

int n,m,in[N],out[N],head[N];
vector <int> g[N],ans;

void dfs(int x)
{
	for(int i=head[x]; i<g[x].size(); i=head[x])
	{
		int y=g[x][i];
		head[x]=i+1;
		dfs(y);
	}
	ans.push_back(x);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		out[x]++;  in[y]++;
	}
	
	bool pd=1;
	int cnta=0,cntb=0,s=1;
	for(int i=1; i<=n; i++)
	{
		if(in[i]==out[i])
			continue;
		pd=0;
		if(in[i]==out[i]-1)
		{
			s=i;
			cnta++;
		}
		else if(in[i]==out[i]+1)
			cntb++;
		else
		{
			printf("No");
			return 0;
		}
	}
	
	if(!pd && !(cnta==cntb && cnta==1))
	{
		printf("No");
		return 0;
	}
	
	for(int i=1; i<=n; i++)
		sort(g[i].begin(),g[i].end());
	
	dfs(s);
	
	for(int i=ans.size()-1; i>=0; i--) //注意是倒序输出
		printf("%d ",ans[i]);		

	return 0;
}