自动搬运

查看原文

来自洛谷，原作者为

	SCP982 **

搬运于2025-08-24 22:17:04，当前版本为作者最后更新于2022-12-30 11:47:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

需要知识点:

• 图的基础知识（有向图&无向图, 图的存储）

• 欧拉回路基础概念

本篇用到知识点

• vector 存储

• 欧拉回路

解析

从 1 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 1 号农场，从一个点出发，每条边都走一遍并回到起点，这是一个经典的欧拉回路问题。由于每条路必须从两个方向各走恰好一遍，所以需要双向建边，本人没有看到任何一篇使用了 vector 存图的新手向题解，所以过来写一篇较朴实无华の新手向题解，只要知道欧拉回路和 vector 是啥就行。

啥是欧拉回路

• 对于无向图，欧拉回路就是在图的所有结点的度都是偶数，并且图是连通的情况下，从任意一个节点开始 dfs 都可以回到原点。

• 对于有向图，欧拉回路就是在图的所有结点的出度和入度都相同，并且图是连通的情况下，从任意一个节点开始 dfs 都可以回到原点。

• 本题明确说明存在欧拉回路，所以不需要判断。

啥是度

• 对于无向图，度就是连接节点的边数（没有 up 会给你解释这个的）

• 对于有向图，出度就以该点为起点的边的条数，入度就是以该点为终点的边的条数。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v;
vector<int> ve[10002];
queue<int> ans;
//这里就是一个朴实无华的深搜，就只是用了欧拉回路的思路，反正他会回来，每次删边就行
void dfs(int f){
	int len=ve[f].size();
	for(int i=0;i<len;++i){
		int xn=ve[f][i];
		if(xn){
			//删边
			ve[f][i]=0;
			dfs(xn);
		}
	}
  	//ans是用来存最终的顺序的
	ans.push(f);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
  		//双向建边
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	//从1号点开始dfs
	dfs(1);		
  	//输出，每次输出都出队
	while(!ans.empty()) {
		printf("%d\n",ans.front());
		ans.pop();
	}
  	//朴实无华的结束
	return 0;
}

对代码的补充说明

在代码第五行我使用了队列来存储最后的答案，这个方法只是偷了个懒，没有算如果用数组最多要开多大，那接下来就算一下。

首先题中明确给出了边的最大数量也就是 $M$（$1 \leq M \leq 5 \times 10^4$），又因为这里每条边要走两次，相当于 $2M$ 条边，从起点出发，每走一条边，就会扩展一个点，再加上起点，欧拉回路最终会有 $2M+1$ 个点，也就是 $100001$ 个点，因为我的数组要从下标一开始存，所以数组的空间要开到 $100002$。