Cod sursa(job #2696702)

Utilizator evelina.nitoiuNitoiu Evelina evelina.nitoiu Data 16 ianuarie 2021 13:37:31
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<bits/stdc++.h>

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

int a[100003],b[100003];
int viz[100003];
vector<int>v[100003];
int n, m;
vector<int> ans;

void citire ()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        in>>a[i]>>b[i];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
}

bool check()
{
    for(int i=1; i<=n; i++)
    {
        if(v[i].size()%2==1)
        {
            return false;
        }
    }
    return true;
}

int euler(int pz)
{
    while(v[pz].size()!=0)
    {
        int muchia_curenta=v[pz].back();
        v[pz].pop_back();
        if(viz[muchia_curenta])
            continue;
        viz[muchia_curenta]=1;
        int vecin;
        if(a[muchia_curenta]==pz)
            vecin=b[muchia_curenta];
        else
            vecin=a[muchia_curenta];
        euler(vecin);
    }
    ans.push_back(pz);
}
int main()
{
    citire();
    if(!check())
    {
        out<<-1<<"\n";
    }
    else
    {
        euler(1);
        ans.pop_back();
        for(int i:ans)
            out<<i<<" ";
    }

    return 0;
}