欧拉路径与欧拉回路

欧拉路径

定义

欧拉路径,指在有向图 G G G 中,可以从起点 v 1 v_1 v1​ 开始,经过每条边,则此路径为欧拉路径。

欧拉回路,就是在欧拉路径的基础上,限定终点也必须为 v 1 v_1 v1

判定方法

欧拉回路,其实就是一笔画问题。而根据我们的小学数学可知,如果一个图可以一笔画,则必须满足以下条件之一:

  • 有两个节点连边个数为奇数
  • 全部节点连边个数为偶数

针对第一条件,则起点就为其中一个奇点,终点为另一个奇点。

第二条件,则起点设在哪里都行,终点也为起点,默认为编号最小的节点。

生成路径

采取 dfs,每次遍历到一个节点,都将其进栈。最后倒序输出即为欧拉路径。

每遍历到一个节点,都需要判断与其的连边是否已经遍历过,没遍历过则继续遍历指向节点。

朴素代码:

//e[i]:链式前向星
// vis:每条边是否遍历过
void dfs(int u)
{
	for(int i=head[u];i;i=e[i].to)//剪枝优化
	{
		if(vis[i]) continue;
         vis[i]=true;
		dfs(edge[i].to);
	}
	st.push(u);
	return;
}
例题:P7771 【模板】欧拉路径

朴素版代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int start=1,inn,outn;
bool vis[M];
struct EDGE{
	int from,to,pre;
}e[M],edge[M];
int head[N],u,v,cnt_edge;
int in[N],out[N];
void add(int from,int to)
{
	edge[++cnt_edge].from=from;
	edge[cnt_edge].to=to;
	edge[cnt_edge].pre=head[from];
	head[from]=cnt_edge;
	return;
}
stack<int> st;
void dfs(int u)
{
	for(int i=head[u];i;i=e[i].to)
	{
		if(vis[i]) continue;
         vis[i]=true;
		dfs(edge[i].to);
	}
	st.push(u);
	return;
}
bool cmp(EDGE a,EDGE b)//简简单单排个序
{
	if(a.from!=b.from)
		return a.from<b.from;
	return a.to>b.to;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].from,&e[i].to);
		in[e[i].to]++;out[e[i].from]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(abs(in[i]-out[i])>1)//出度与入度差>1,直接排除
		{
			printf("No\n");
			return 0;
		}
		if(in[i]-out[i]==1)//入度比出度多一,为终点
			inn++;//有多少个可以为终点
		if(out[i]-in[i]==1)//起点,并标记
		{
			outn++;//有多少个可以为起点
			start=i;
		}
	}
	if((inn==0&&outn==0)||(inn==1&&outn==1))//上文所述的两种判定方法
	{
		sort(e+1,e+m+1,cmp);
		for(int i=1;i<=m;i++)
			add(e[i].from,e[i].to);
		dfs(start);
		while(!st.empty())
		{
			printf("%d ",st.top());
			st.pop();
		}
	}
	else
		printf("No");
	putchar('\n');
	return 0;
}

然而,实测只有 90 p t s 90pts 90pts,原因是 dfs 中的遍历没有剪枝,浪费时间。

优化办法:遍历时直接更新 head 数组,免得每次都得遍历 m m m 次。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int start=1,inn,outn;
bool vis[M];
struct EDGE{
	int from,to,pre;
}e[M],edge[M];
int head[N],u,v,cnt_edge;
int in[N],out[N];
void add(int from,int to)
{
	edge[++cnt_edge].from=from;
	edge[cnt_edge].to=to;
	edge[cnt_edge].pre=head[from];
	head[from]=cnt_edge;
	return;
}
stack<int> st;
void dfs(int u)
{
	for(int i=head[u];i;i=head[u])
	{
		head[u]=edge[i].pre;
		dfs(edge[i].to);
	}
	st.push(u);
	return;
}
bool cmp(EDGE a,EDGE b)
{
	if(a.from!=b.from)
		return a.from<b.from;
	return a.to>b.to;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].from,&e[i].to);
		in[e[i].to]++;out[e[i].from]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(abs(in[i]-out[i])>1)
		{
			printf("No\n");
			return 0;
		}
		if(in[i]-out[i]==1)
			inn++;
		if(out[i]-in[i]==1)
		{
			outn++;
			start=i;
		}
	}
	if((inn==0&&outn==0)||(inn==1&&outn==1))
	{
		sort(e+1,e+m+1,cmp);
		for(int i=1;i<=m;i++)
			add(e[i].from,e[i].to);
		dfs(start);
		while(!st.empty())
		{
			printf("%d ",st.top());
			st.pop();
		}
	}
	else
		printf("No");
	putchar('\n');
	return 0;
}

相关推荐

  1. 路径

    2024-07-22 05:18:04       28 阅读
  2. C++的算法:道路

    2024-07-22 05:18:04       31 阅读
  3. 1184. ,模板题)

    2024-07-22 05:18:04       75 阅读
  4. [Tricks] 记各类问题

    2024-07-22 05:18:04       49 阅读
  5. ROS

    2024-07-22 05:18:04       66 阅读
  6. 【数论】

    2024-07-22 05:18:04       43 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 05:18:04       138 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 05:18:04       152 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 05:18:04       128 阅读
  4. Python语言-面向对象

    2024-07-22 05:18:04       140 阅读

热门阅读

  1. Linux grep技巧 提取log中的json数据

    2024-07-22 05:18:04       27 阅读
  2. Python 异常处理

    2024-07-22 05:18:04       25 阅读
  3. Python中的__new__方法及实现单例模式

    2024-07-22 05:18:04       31 阅读
  4. FlowUs横向对比几款笔记应用的优势所在

    2024-07-22 05:18:04       32 阅读
  5. 公式推导类

    2024-07-22 05:18:04       29 阅读
  6. 【C++】C++内存泄漏介绍及解决方案

    2024-07-22 05:18:04       25 阅读
  7. 后台接口的配置

    2024-07-22 05:18:04       28 阅读
  8. Optional 中 map 和 flatMap 区别是啥?

    2024-07-22 05:18:04       25 阅读
  9. 实习手计(4):月末碎碎念!

    2024-07-22 05:18:04       18 阅读
  10. Nginx详细配置(最佳实践)

    2024-07-22 05:18:04       30 阅读