1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define maxn 5010
using namespace std;
int n, m;
vector<int> G[maxn];
void dfs(int u, int fa, int x, int y, vector<int> &ans) {
ans.push_back(u);
for (auto v : G[u]) {
if (v == fa || u == x && v == y || u == y && v == x) continue;
dfs(v, u, x, y, ans);
}
}
stack<int> S; int a[maxn], cnt;
bool Dfs(int u, int fa) {
static bool vis[maxn] = { 0 };
vis[u] = 1; S.push(u);
for (auto v : G[u]) {
if (v == fa) continue;
if (vis[v]) {
int t;
do {
t = S.top(); S.pop();
a[++cnt] = t;
} while (t != v);
return 1;
}
if (Dfs(v, u)) return 1;
} S.pop(); return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
G[x].push_back(y); G[y].push_back(x);
}
for (int i = 1; i <= n; ++i) sort(G[i].begin(), G[i].end());
if (m == n - 1) {
vector<int> ans; dfs(1, 0, 0, 0, ans);
for (auto u : ans) cout << u << " ";
}
else {
Dfs(1, 0);
vector<int> A; dfs(1, 0, a[1], a[cnt], A);
for (int i = 1; i < cnt; ++i) {
vector<int> B; dfs(1, 0, a[i], a[i + 1], B);
if (B < A) A = B;
}
for (auto u : A) cout << u << " ";
}
return 0;
}
|