题目分析

本题中，小约翰尼要在镇上开车拜访朋友，每条街道有一个朋友，他要设计一个环形行程，每条街道只走一次并回到起点，且要找到字典序最小的环形行程，如果不存在这样的行程则输出特定信息。输入是街道连接的路口编号和街道编号，输出是符合要求的街道编号序列或不存在行程的提示。

算法标签

图论 - 欧拉回路：题目要求每条街道只走一次并回到起点，这符合图论中欧拉回路的概念，即从一个顶点出发，经过每条边恰好一次并回到起点的回路。 深度优先搜索（DFS）：在寻找欧拉回路的过程中，深度优先搜索算法可以用于遍历图的边，找到符合条件的路径。并且在本题中，为了找到字典序最小的环形行程，DFS 可以按照一定顺序遍历边，以满足字典序的要求。 回溯法：当在搜索过程中发现当前路径无法构成欧拉回路时，需要回溯到上一个状态，尝试其他路径，这体现了回溯法的思想。

解题思路

构建图结构：根据输入的 x（路口编号）、y（路口编号）和 z（街道编号）信息，构建一个图结构，例如使用邻接表来存储图，记录每个路口连接的街道以及每条街道连接的两个路口。 判断是否存在欧拉回路：根据图论知识，一个图存在欧拉回路的充要条件是图中每个顶点的度数都是偶数。遍历图的顶点，检查每个顶点的度数，如果存在度数为奇数的顶点，则不存在欧拉回路，直接输出 “Round trip does not exist.”。 使用 DFS 寻找欧拉回路：如果图存在欧拉回路，从输入中第一条街道连接的较小编号的路口开始进行深度优先搜索。在 DFS 过程中，对于每个顶点，按照街道编号从小到大的顺序遍历其邻接边，确保找到的欧拉回路是字典序最小的。 在遍历边时，将已访问的边标记为已使用，避免重复访问。 当遍历完所有边且回到起点时，记录下当前的街道编号序列。 回溯处理：如果在 DFS 过程中发现当前路径无法构成欧拉回路（例如遍历完所有顶点但边未全部访问完），则回溯到上一个顶点，尝试其他未访问的边。 输出结果：如果成功找到欧拉回路，输出记录的街道编号序列；如果经过回溯等操作后仍未找到，则输出 “Round trip does not exist.”。

代码实现步骤（c++）

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring> 
using namespace std;
const unsigned MaxJunc = 45;
const unsigned MaxStreet = 2000;
typedef struct _JUNC
{
	vector<unsigned> street;
}Junc;
 
int main()
{
	Junc junc[MaxJunc];
	unsigned street[MaxStreet][2];
	unsigned streetCnt, maxJuncNum;
	vector<unsigned> output;
	unsigned x,y,z;
	int i;
 
	while(1)
	{
		memset(junc, 0, sizeof(struct _JUNC)*MaxJunc);
		memset(street, 0, sizeof(unsigned)*MaxStreet*2);
		streetCnt = 0;
		maxJuncNum = 0;
 
		cin>>x>>y;
		if(x==0 && y==0)
			break;
		while(x!=0 && y!=0)
		{
 
			cin>>z;
			junc[x].street.push_back(z);
			junc[y].street.push_back(z);
			street[z][0] = x;
			street[z][1] = y;
			++streetCnt;
			if(x<y)
				maxJuncNum = maxJuncNum>y?maxJuncNum:y;
			else
				maxJuncNum = maxJuncNum>x?maxJuncNum:x;
			cin>>x>>y;
		}
		for(i=1; i<=maxJuncNum ; ++i)
		{
			vector<unsigned> tmp(junc[i].street.size());
			if(junc[i].street.size())
			{
				for(int j=0; j<junc[i].street.size(); ++j)
					tmp[j] = junc[i].street[j];
 
				sort(tmp.begin(),tmp.end());
				for(int j=0; j<junc[i].street.size();++j)
					junc[i].street[j] = tmp[j];
			}
		}
		
		i = 1;
		while(junc[i].street.size())
		{
			unsigned j = 0;
			unsigned visit;
			for(;j<junc[i].street.size(); ++j)//找的从junc[i]出发将要去的下一条street
			{
				if(junc[i].street[j]!=0)
				{
					visit = junc[i].street[j];
					junc[i].street[j] = 0;
					break;
				}
			}
			if(j==junc[i].street.size())
				break;
			output.push_back(visit);
			i = (i==street[visit][0])?street[visit][1]:street[visit][0];//跳到当前访问的street的另一端
			for(unsigned k=0; k<junc[i].street.size(); ++k)//将另一端中对应的该条street置为0
			{
				if(junc[i].street[k]==visit)
				{
					junc[i].street[k] = 0;
					break;
				}
			}
		}
		if(output.size()!= streetCnt)
			cout<<"Round trip does not exist."<<endl;
		else
		{
			cout<<output[0];
			for(i=1; i<output.size(); ++i)
				cout<<" "<<output[i];
			cout<<endl;
		}
		output.clear();
	}
	return 0;
}