[usaco05jan]watchcow s (Euler loop)

[USACO05JAN]Watchcow S

Title Description

Farmer John Yes $N$ A farm （$2\le N\le 10^4$）, These farms are owned by $M$ Two roads connect （$1\le M\le 5\times 10^4$）. There is no guarantee that there is no heavy edge .

Bassie from $1$ Farm No. 1 starts patrolling , Each road must go in two directions Just once , Finally back to $1$ Farm No .

Please output a path that meets the above requirements .

Ensure that such a path exists . If there are multiple paths , Just output any one .

Input format

The first line has two integers $N,M$.

Next $M$ That's ok , Two integers per line $u,v$, Describe a $u$ To $v$ The path of .

Output format

Output through the farm , A line of one .

Examples #1

The sample input #1

4 5
1 2
1 4
2 3
2 4
3 4

Sample output #1

1
2
3
4
2
1
4
3
2
4
1

Ideas ：

Undirected graph to directed graph --> Euler loop of running digraph

AC The code is as follows ：

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1e4 + 9, M = 1e5 + 9;
int n, m;
int e[M], h[M], ne[M], idx;
int s[M], cnt;
bool st[M];****
void add(int a, int b)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int x)
{
    
    for (int i = h[x]; ~i; i = ne[i])
    {
    
        if (!st[i])
        {
    
            st[i] = true;
            int j = e[i];
            dfs(j);
            s[++cnt] = j;
        }
    }
}
void solve()
{
    
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
    
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1);
    s[++cnt] = 1;
    for (int i = cnt; i >= 1; i--)
        cout << s[i] << '\n';
}
int main()
{
    
    buff;
    solve();
}