题目
问题描述
为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。
任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。每个交叉路口都至少连接着一条街道，有的交叉路口可能只连接着一条或两条街道。
小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。输入格式
输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。
接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。输出格式
如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, ..., pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。
如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。
评测用例规模与约定
前30%的评测用例满足：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20。
前50%的评测用例满足：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000。
所有评测用例满足：1 ≤ n ≤ 10000，n-1 ≤ m ≤ 100000。
题目解释
这题要求的是一个欧拉通路（能够不重复且遍历所有边的路径）
欧拉通路存在的充要条件：对于无向图来说，度数为奇数的的点可以有2个或者0个，并且这两个奇点其中一个为起点另外一个为终点。对于有向图来说，可以存在两个点，其入度不等于出度，其中一个入度比出度大1，为路径的起点；另外一个出度比入度大1，为路径的终点。
这题显然是无向图，只需要判断度数为奇数的点是0还是2还是其他（无欧拉通路）
求解欧拉通路的一个主流办法就是Fleury算法
Fleury算法
该算法默认给出的点和边存在欧拉通路
首先根据度的约束，找到算法的起点
算法的核心思想：对于每个遍历到的点，找到下一个连接处（然后直接开始对下一个点操作），如果没有则入栈（最后显示路径结果时体现为该点出现在靠后，也就是说第一个入栈的一定为第一个无可连通点的点）
每次找到的点要减掉两点之间的连通度（可能两点间存在多条边）
由于我们只要找字典序最小的，所以每次找可连通点，从1往n遍历即可
80分代码（内存超限，最后的样例估计不报mle也会tle）
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
vector<vector<int>>v;
vector<int>d;
int n, m;
stack<int>s;
void build() {
cin >> n >> m;
d = vector<int>(n + 1, 0);
v = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a][b] = 1;
v[b][a] = 1;
d[a]++;
d[b]++;
}
}
void dfs(int start) {
for (int i = 1; i <= n; i++) {
if (v[start][i]) {
v[start][i]--;
v[i][start]--;
dfs(i);
}
}
s.push(start);
// stack<int> st;
// st.push(start);
//
// while (!st.empty()) {
// int var = st.top();
// bool found = false;
//
// for (int i = 1; i <= n; i++) {
// if (v[var][i]) {
// v[var][i]--;
// v[i][var]--;
// st.push(i);
// found = true;
// break;
// }
// }
// if (!found) {
// s.push(var);
// st.pop();
// }
// }
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
build();
int cnt = 0, start = 0;
for (int i = 1; i <= n; i++) {
if (d[i] & 1) { //记录奇点个数 同时如果满足存在欧拉通路条件，第一个奇点作为起点可以满足字典序最小的条件
cnt++;
if (start == 0)start = i;
}
}
if (cnt == 1 || cnt > 2) {
cout << -1;
} else {
if (start == 0)start = 1; //不存在奇点的话直接1起点
dfs(start);
if (s.size() != m + 1)cout << -1; // 判断是否存在图不连通的情况，如果连通最后的路径一定是m+1个点
else {
for (int i = 1; i <= m + 1; i++) {
if (i != 1)cout << " ";
cout << s.top();
s.pop();
}
}
}
return 0;
}虽然注意到了有另一种有向图的算法，但是不知在这题可不可行，由于点的数量会到1e4，边的数量会到1e5，邻接表不方便操作，而邻接图又太耗内存。且dfs里每次的for循环时间开销也不小
期待一个邻接表的做法能ac这道题，有80分还是很心满意足的
