问题描述
输入格式
输出格式
数据范围
输入样例1：
4 5 1 2 1 3 1 4 2 4 3 4
输出样例1：
1 2 4 1 3 4
样例1解释
城市的地图和小明的路径如下图所示。
输入样例2：
4 6 1 2 1 3 1 4 2 4 3 4 2 3
输出样例2：
-1
样例2解释
城市的地图如下图所示，不存在满足条件的路径。
本题链接：http://118.190.20.162/view.page?gpid=T34
AC代码
C++
#include <iostream> #include <cstring> #include <algorithm> #include <set> using namespace std; const int N = 10010, M = 100010; int n, m; set<int> g[N]; int p[N]; int ans[M], top; int find(int x) // 并查集 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void dfs(int u) { while (g[u].size()) { int t = *g[u].begin(); g[u].erase(t), g[t].erase(u); // 删边 dfs(t); } ans[ ++ top] = u; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化p数组 while (m -- ) { int a, b; scanf("%d%d", &a, &b); g[a].insert(b), g[b].insert(a); p[find(a)] = find(b); } int s = 0; for (int i = 1; i <= n; i ++ ) if (find(i) != find(1)) // 不是连通图 { puts("-1"); return 0; } else if (g[i].size() % 2) s ++ ; // s记录的是度数为奇数的点的 // 度数为奇数的点不是0个或2个，或者度数为奇数的点为2个但是起点的度数不是奇数，则不符合欧拉路径 if (s != 0 && s != 2 || s == 2 && g[1].size() % 2 == 0) { puts("-1"); return 0; } dfs(1); // 开始遍历欧拉路径 for (int i = top; i; i -- ) // 欧拉路径实际上记录的是倒序，故求正向欧拉路径需要逆序输出 printf("%d ", ans[i]); return 0; }
java
注：java版代码只有50分
import java.util.*; public class Main { final int N = 100010; int n, m; int[] ans = new int[N]; int top; int[] p = new int[10010]; TreeSet[] g = new TreeSet[10010]; void run() { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for (int i = 0; i <= n; i++) { g[i] = new TreeSet(); } for (int i = 1; i <= n; i++) { p[i] = i; } while (m -- != 0) { int a, b; a = sc.nextInt(); b = sc.nextInt(); g[a].add(b); g[b].add(a); p[find(a)] = find(b); } int s = 0; for (int i = 1; i <= n; i++) { if (find(i) != find(1)) { System.out.println("-1"); return; } else if (g[i].size() % 2 != 0) { s++; } } if (s != 0 && s != 2 || (s == 2 && g[1].size() % 2 == 0)) { System.out.println("-1"); return; } dfs(1); for (int i = top; i != 0; i--) { System.out.printf("%d ", ans[i]); } } void dfs(int u) { while (g[u].size() != 0) { int t = (Integer) g[u].first(); g[u].remove(t); g[t].remove(u); dfs(t); } ans[ ++ top] = u; } int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } public static void main(String[] args) { new Main().run(); } }
代码解释
从一个点出发，不重不漏的经过图中每一条边的一条路径（允许多次经过同一个点）。
从一个点出发，不重不漏的经过图中每一条边的一条路径（允许多次经过同一个点）。如果此路径的起点和终点相同，则称其为一条欧拉回路。
入度(indegree)就是有向图中指向这个点的边的数量，即有向图的某个顶点作为终点的次数和
出度(outdegree)就是从这个点出去的边的数量，即有向图的某个顶点作为起点的次数和
一个点的度（degree）指图中与该点相连的边数
无向连通图
欧拉回路：所有点的度数都为偶数即为有欧拉回路
欧拉路径：度数为奇数的点要么有2个要么有0个
若为0个那么从任意点出发都可以，如果有2个，那么起点必须是其中一个点，终点必须为另一个点
有向连通图
欧拉回路：所有点的入度等于出度
欧拉路径：1.所有点的入度等于出度 2.有一个点(终点)的入度=出度+1，且存在一个点(起点)的出度=入度+1
从当前点出发，只要有出去的边就往外走，深度优先遍历，回溯路径就是它的一个方案
为什么从起点搜到终点不是一个方案？
因为在搜索的过程中，不一定会把所有的边全部走到（有一堆额外的环），但因为起点和终点是唯一的，
且其余点的度数均为偶数，故我们在回溯的过程中把其他的结点（那些没有走过的环）补充到搜索图中即可
字典序最小：从当前点出去搜的时候，按照编号从小到大搜索一遍，就可以保证字典序最小
欧拉路径证明（无向图）
对于起点而言，设其度数为n，那么起始往出走需要一条边，其余到达起点的话，就必然是进来一次出去一次，故起点的度数必须是奇数
对于终点而言，设其度数为m，那么最终到达需要一条边，其余到达终点的点，需要再次出去，故终点的度数必须是奇数
对于非起点和非终点的其余点，它们只是作为中间的“桥梁”，故到达这些点后还需要离开，故这些点的度数必须是偶数
如果起点和终点是同一个点，那么对于起点（终点）而言，出去需要一条边，最终到达该点需要一条边，其余时候进来必然还要出去，
故在这种情况下，起点（终点）的度为偶数
综上所述，对于一个无向图的欧拉路径而言，度数为奇数的点要么为2个要么为0个，且为2个的时候，这两个点分别做起点和终点
dfs(u) // 求得的序列其实是欧拉路径的倒序序列 { for u的所有边 dfs() // 扩展 seq += u // 把u加到序列中 }
欧拉路径dfs和一般图论dfs区别：
一般图论dfs用点来判重，时间复杂度在O(n+m)
欧拉路径是用边来判重，如果用一个bool变量来表示每个边是否被搜过，时间复杂度会很高：
举个例子，对于一个点，假设其有m条自环，那么我们在遍历的过程中搜第一条边，搜完之后又回到该点，
此时第一条边已经被用过了，故我们要跳过这一条边搜第二条边，依次类推，在搜第三条边的时候需要跳过第一条边和第二条边
以此类推，在搜完m条边的时候就会跳m^2次，这样对于1e5的数据量显然就会超时
处理方法：每用一条边不是进行简单的标记，而是直接进行删除，这样就可以降为线性时间复杂度
无向图的删除方法：因为建无向图对于每一条边会建立两次（不同方向），故我们在删除的时候还需要对它的反向边进行一次标记
如何根据一条边找到它的反向边：因为建边的时候是按照(0,1),(2,3)…进行建边，故求反向边可直接根据 i^1 求得
上述代码中并未采取这种建边方式，直接把边放入set中，set自然有序，且易直接删边
