Cod sursa(job #2972513)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 29 ianuarie 2023 16:57:49
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100004;
const int MMAX = 500004;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n, m;
vector<pair<int, int>> adj[NMAX];
bool used_edge[MMAX];
stack<int> S;

vector<int> euler_cycle(int s)
{
    vector<int> res;
    S.push(s);
    while (!S.empty())
    {
        int v = S.top();
        if (adj[v].size() > 0)
        {
            int u = adj[v].back().first;
            int ind = adj[v].back().second;
            adj[v].pop_back();
            if (!used_edge[ind])
            {
                used_edge[ind] = true;
                S.push(u);
            }
        }
        else
        {
            res.push_back(v);
            S.pop();
        }
    }
    return res;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    for (int i = 1; i <= n; i++)
    {
        if (adj[i].size() % 2 == 1)
        {
            fout << -1;
            return 0;
        }
    }
    vector<int> res = euler_cycle(1);
    res.pop_back();
    for (int v : res)
    {
        fout << v << ' ';
    }
    return 0;
}