问题描述 　　为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。 　　任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。每个交叉路口都至少连接着一条街道，有的交叉路口可能只连接着一条或两条街道。 　　小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。 输入格式 　　输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。 　　接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。 输出格式 　　如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p₁, p₂, p₃, ..., p_m+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p₁最小，p₁最小的前提下再保证p₂最小，依此类推。 　　如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。 样例输入 4 5 1 2 1 3 1 4 2 4 3 4 样例输出 1 2 4 1 3 4 样例说明 　　城市的地图和小明的路径如下图所示。 样例输入 4 6 1 2 1 3 1 4 2 4 3 4 2 3 样例输出 -1 样例说明 　　城市的地图如下图所示，不存在满足条件的路径。 评测用例规模与约定 　　前30%的评测用例满足：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20。 　　前50%的评测用例满足：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000。 　　所有评测用例满足：1 ≤ n ≤ 10000，n-1 ≤ m ≤ 100000。

——————————————————————————————————

1、知识梳理

这题涉及的知识是离散数学里的欧拉图，从一个顶点出发，经过图中每条边一次且仅有一次，并且行遍图中所有顶点。题目说明了存在无解的情况，所以要判断这个图是否存在欧拉回路或者欧拉通路。 如果一个图是欧拉回路，当且仅当是连通图且无奇度顶点。无向图中，一个顶点度的大小就是这个顶点所连接边的数量。如果一个图是欧拉通路，当且仅当这个图是连通的且恰好有两个奇度顶点，并且端点要在这两个顶点上。 所以说，对于这题，我们要先做一下判断： 是连通图不存在奇数顶点或者存在两个奇数顶点如果存在两个奇数顶点，节点1一定是奇数顶点 只要有一条不满足，就给可以输出-1。都满足的话就可以做深度搜索，寻找路径了。

2、要点提示

DFS不用多说大家都会，这里用vector建立邻接表，用一个二维数组存储是否已经访问过某条边的信息，但是这题搜索记录点的策略有所不同。最初我是用一个队列，每到一个节点就把这个节点加入队列中，结束深搜后依次输出。结果只有20分。。。。。代码检查了很久一点问题都没有，看了别人的代码，又研究了很久，唯一的区别就是AC的代码是用栈，在递归回来之后才将该节点添加入栈，相当于倒序储存了。想着和用队列顺序存也没什么差别呀。嗯嗯对于正常的图确实一样，但是我开始忽略了一种存在孤点的图。如下图所示： 图中点2 是孤立点，如果每次搜索到一个节点就存储进队列的话，就会出现错误，而用栈，倒序存就能解决这个问题。不过因为这种情况没考虑到，给扣了80分，CCF也太狠了。 代码如下： #include<iostream> #include<vector> #include<queue> #include<algorithm> #include<stack> using namespace std; #define MAXX 10010 int n,m; bool get[MAXX],node[MAXX][MAXX]; vector<int> vec[MAXX]; stack<int> st; queue<int> q; bool cmp(int a,int b)//从小到大排序 { if(a<b) { return true; } else { return false; } } void DFS(int x)//x表示当前走到的节点，t表示是第几个节点 { for(int i=0;i<(int)vec[x].size();i++) { int y=vec[x][i]; if( !node[x][y]) { node[x][y] = true; node[y][x] = true; //q.push(y); DFS(y); st.push(y); } } } //判断是否是连通的 void Judge(int x) { int y; get[x] = true; for(int i=0;i<(int)vec[x].size();i++) { y = vec[x][i]; if(!get[y]) { Judge(y); } } } int main() { int x,y; cin >> n >> m; for(int i=0;i<m;i++) { cin >> x >> y; vec[x].push_back(y);//邻接表 vec[y].push_back(x); } //判断是否是欧拉回路 int count=0,size=0; for(int i=1;i<=n;i++) { size = (int)vec[i].size(); if(size%2==1) { count++; } sort(vec[i].begin(),vec[i].end());//排好序，为下面dfs做准备 } if(count>2 || count==1)//奇数度顶点大于2或者等于1则不是欧拉回路 { cout << "-1" ; return 0; } //如果奇数度等于2，则起点一定要在奇数度点上 if(count == 2) { if(vec[1].size()%2!=1) { cout << "-1"; return 0; } } //判断是否是连通图 Judge(1); for(int i=1;i<=n;i++) { if(!get[i]) { cout << "-1"; return 0; } } //搜索路径 DFS(1); //用队列顺序储存，错误 /* cout << 1; while(!q.empty()) { cout <<" " << q.front() ; q.pop(); } cout << endl;*/ //用栈逆序存储，正确 cout << 1; while(!st.empty()) { cout<<" " << st.top(); st.pop(); } cout << endl; return 0; }