小码匠的信息学江湖【第83式】：欧拉回路之[USACO05JAN] Watchcow S

小码匠

发布于 2023-09-06 14:20:39

2450

发布于 2023-09-06 14:20:39

文章被收录于专栏：小码匠和老码农

对话

老码农总是喜欢揪住细节不放，这道题虽然2次AC了，但被他一直追问

明明留了4道题，为啥先捡黄题做（其实是老码农给记错了，他原来以为是三道绿题，1道蓝题。真是，有黄题不做，我自虐啊。）
为啥第一次MLE了？为啥第一次MLE了？为啥第一次MLE了？

题解处有关于MLE的分享

题目描述

Farmer John 有 N 个农场（

2≤N≤10^4

），这些农场由 M 条道路连接（

1≤M≤5×10^4

）。不保证没有重边。

Bassie 从 1 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 1 号农场。

请输出一条满足上述要求的路径。

保证这样的路径存在。如果有多条路径，任意输出一条即可。

输入格式

第一行两个整数 N,M。

接下来 M 行，每行两个整数 u,v，描述一条 u 到 v 的道路。

输出格式

输出经过的农场，一行一个。

输入输出样例

输入 #1复制

输出 #1复制

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P6066
- 参考题解：https://www.luogu.com.cn/problem/P6066
标签：OI、图论、欧拉回路

正解

先放一个oi_wiki的链接 —>欧拉图相关基础知识
思路很简单，首先这是一个无向图且题目保证路径存在，所以判断回路这里就可以免了
就是套一下欧拉回路的模板，无向图所以要双向建边的，然后每次走过一条边就删掉这条边，我用的是邻接表，然后开了bool数组判定这条边走没走过
但是，我空间爆了！！！所以我用了结构体去存，空间就OK啦，当然直接开二维数组MLE也不排除是我太懒把AC的模版拷过来然后还没改MAXN的数据范围，不过改小了能不能过我倒是不知道啦，大家可以试一试

MLE

// 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;
}

AC代码

// 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-09-04，如有侵权请联系 cloudcommunity@tencent.com 删除

cin