Cod sursa(job #3269698)

Utilizator andreea0146Nicula Andreea andreea0146 Data 20 ianuarie 2025 15:46:48
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;

const int NMAX=100001,MMAX=500001;

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

int n,m;
vector<int>g[NMAX+1],l;
vector<pair<int,int>>M;
vector<bool>elim;

void euler(int v)
{
    for(int &x : g[v])
        if(!elim[x])
        {
            elim[x]=1;
            int p=M[x].second;
            if(p==v) p=M[x].first;
            euler(p);
        }
    l.push_back(v);
}

bool verif()
{
    for (int i=1; i<=n; i++)
        if(g[i].size()%2!=0)
            return 0;
    return 1;
}

int main()
{
    int x, y;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>x>>y;
        M.push_back(make_pair(x,y));
        elim.push_back(0);
        g[x].push_back(M.size()-1);
        g[y].push_back(M.size()-1);
    }

    if(!verif())
        fout<<"-1";
    else
    {
        euler(1);
        for (const int&x:l)
            fout<<x<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}