Cod sursa(job #3169540)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 15 noiembrie 2023 12:05:19
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#define nod_sz 100000
#define mch_sz 500000

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

struct muchie{
int x;
int ind;
};
int mk;

vector <muchie> v[nod_sz+5];
bool viz[mch_sz+5];
int gr[nod_sz+5];



int sol[mch_sz+5];
int solk;

void dfs(int nod)
{
    while(!v[nod].empty()){
        muchie i = v[nod].back();
        v[nod].pop_back();
        if(!viz[i.ind]){
            viz[i.ind]=true;
            dfs(i.x);
        }

    }
    sol[++solk]=nod;
}


int n;
int main()
{
    fin.tie(0);
    fout.tie(0);
    ios::sync_with_stdio(false);
    fin>>n>>mk;
    for(int i=1;i<=mk;i++)
    {
        int x,y;
        fin>>x>>y;
        gr[x]++;
        gr[y]++;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    for(int i=1;i<=n;i++)
        if(gr[i]%2)
    {
        fout<<-1;
        return 0;
    }
    dfs(1);
    for(int i=1;i<solk;i++)
        fout<<sol[i]<<' ';
}