Cod sursa(job #2723215)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 13 martie 2021 19:22:56
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

typedef pair < int, int > PII;

const int NMAX = 1e5 + 1, MMAX = 5e5 + 1;
const int ROOT = 1;

int N, M;

vector < PII > G[NMAX];

bool Sel[MMAX];

vector < int > Sol;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int X = 0, Y = 0;
        f >> X >> Y;

        G[X].push_back({Y, i});
        G[Y].push_back({X, i});
    }

    return;
}

static inline void DFS (int Node)
{
    while(!G[Node].empty())
    {
        auto it = G[Node].back();
        G[Node].pop_back();

        if(!Sel[it.second])
        {
            Sel[it.second] = 1;

            DFS(it.first);
        }
    }

    Sol.push_back(Node);

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
        if(((int)G[i].size()) & 1)
        {
            g << -1 << '\n';

            return;
        }

    DFS(ROOT);

    for(int i = (int)Sol.size() - 1; i >= 1; --i)
    {
        g << Sol[i];

        if(i != 1)
            g << ' ';
    }

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}