老码农总是喜欢揪住细节不放,这道题虽然2次AC了,但被他一直追问
题解处有关于MLE的分享
Farmer John 有 N 个农场(
),这些农场由 M 条道路连接(
)。不保证没有重边。
Bassie 从 1 号农场开始巡逻,每条路必须从两个方向各走恰好一遍,最后回到 1 号农场。
请输出一条满足上述要求的路径。
保证这样的路径存在。如果有多条路径,任意输出一条即可。
第一行两个整数 N,M。
接下来 M 行,每行两个整数 u,v,描述一条 u 到 v 的道路。
输出经过的农场,一行一个。
输入 #1复制
4 5
1 2
1 4
2 3
2 4
3 4
输出 #1复制
1
2
3
4
2
1
4
3
2
4
1
题目原文请移步下面的链接
OI
、图论
、欧拉回路
// Copyright (C) 2021-2028 coder-oldgeek.com All rights reserved.
// 题目: [USACO05JAN] Watchcow S
// 链接: https://www.luogu.com.cn/problem/P6066
// 难度: 普及+/提高
// 提交:
// 题解:
// - https://www.luogu.com.cn/problem/solution/P6066
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
int MAXN = 100010;
int vis[100010];
stack<int> st;
vector<vector<int>> g(MAXN);
vector<vector<bool>> is(MAXN, vector<bool>(MAXN));
void dfs(int now) {
for (int i = vis[now]; i < g[now].size(); i = vis[now]) {
vis[now] = i + 1;
if(is[now][g[now][i]]) {
continue;
}
is[now][g[now][i]] = true;
dfs(g[now][i]);
}
st.push(now);
}
void best_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
while (!st.empty()) {
cout << st.top() << endl;
st.pop();
}
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
// Copyright (C) 2021-2028 coder-oldgeek.com All rights reserved.
// 题目: [USACO05JAN] Watchcow S
// 链接: https://www.luogu.com.cn/problem/P6066
// 难度: 普及+/提高
// 提交:
// 题解:
// - https://www.luogu.com.cn/problem/solution/P6066
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
int MAXN = 100010;
int vis[100010];
struct node {
int to, is;
};
stack<int> st;
vector<vector<node>> g(MAXN);
void dfs(int now) {
for (int i = vis[now]; i < g[now].size(); i = vis[now]) {
vis[now] = i + 1;
if(g[now][i].is) {
continue;
}
g[now][i].is = true;
dfs(g[now][i].to);
}
st.push(now);
}
void best_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back({v, false});
g[v].push_back({u, false});
}
dfs(1);
while (!st.empty()) {
cout << st.top() << endl;
st.pop();
}
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}