#include using namespace std; const int N = 100010, M = N << 2; typedef pair PII; #define a first #define b second int n, m; // n个节点,m条边 PII g[M]; // 用于排序边的临时数组 int start; // 起点 int din[N], dout[N]; // 入度与出度 int res[M], rl; // 记录欧拉路径 // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void dfs(int u) { for (int i = h[u]; ~i; i = h[u]) { // 删边,链表头指向了下一条边 h[u] = ne[i]; // 删边,链表头指向了下一条边 dfs(e[i]); // 处理子节点 } res[++rl] = u; // 这个点是在循环外加入路径的,注意,与边的那份代码可不一样啊! } // 黄海总结的有向图找起点的代码模板,注意每题中起始和终止不一样,i=0,还是i=1需要根据题目而定 int getStart() { int st = 0, a = 0, b = 0, c = 0; for (int i = 1; i <= n; i++) { // 枚举每个有效节点,每道题的具体实现可能有差异 if (dout[i] != din[i]) a++; // 出度与入度不一致的数量 if (dout[i] == din[i] + 1) b++, st = i; // 起点数量,记录起点 if (dout[i] == din[i] - 1) c++; // 终点数量 } if (a && (b != 1 || c != 1)) return -1; // 如果有不一致的,并且不是1个,则没有欧拉路径 // 如果是一个环,也是存在欧拉路径的,但所有点的入度和出度一致,st不会被改写,需要再手找出起点。 while (!dout[st]) st++; return st; } int main() { #ifndef ONLINE_JUDGE freopen("P7771.in", "r", stdin); #endif // 初始化链式前向星 memset(h, -1, sizeof h); // n个顶点,m条边 scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) scanf("%d %d", &g[i].a, &g[i].b); // 用一个PII(点对)的数组先把边保存下来,排序完后,再存入链式前向星中 sort(g, g + m, greater()); // 一维由大到小排序,如果一维一样,那么二维也是由大到小排序。如此,则最后一个遍历到的就是字典序最小的 for (int i = 0; i < m; i++) { add(g[i].a, g[i].b); // 排序完再用链式前向星建图 dout[g[i].a]++, din[g[i].b]++; // 有向图,维护入度和出度 } int start = getStart(); if (start == -1) { puts("No"); return 0; } dfs(start); // 输出欧拉路径 for (int i = rl; i; i--) printf("%d ", res[i]); return 0; }