看牛

AcWing-366-看牛

分析

见《进阶指南》第411页。

实现

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

const int N = 100010, M = 500010;
struct edge {
    int to, next;
};
edge e[2 * M];
int idx, head[N];
int n, m;
stack<int> s, r;

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void euler () {
    s.push(1);
    while (!s.empty()) {
        int cur = s.top(), i = head[cur];
        if (i != -1) {
            s.push(e[i].to);
            head[cur] = e[i].next;
        } else {
            s.pop();
            r.push(cur);
        }
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }

    euler();
    while (!r.empty()) {
        printf("%d\n", r.top());
        r.pop();
    }
    return 0;
}