Cod sursa(job #3122785)

Utilizator RORO123bBarbulescu Robert RORO123b Data 20 aprilie 2023 17:53:49
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>

using namespace std;

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

struct muchie
{
    int x, y;
}e[500001];

bool sterse[500001];

int prim[100001];
vector<int> a[100001],ce;

int n,m;

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

int celalaltvf(muchie e,int x)
{
    return (e.x+e.y-x);
}

void rezolv(int x)
{
    while(prim[x]<(int)a[x].size())
    {
        int i_e_c = a[x][prim[x]++];
        muchie e_c=e[i_e_c];
        int y=celalaltvf(e_c,x);
        if(!sterse[i_e_c])
        {
            sterse[i_e_c]=1;
            rezolv(y);
        }
    }
    ce.push_back(x);
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>e[i].x>>e[i].y;
        a[e[i].x].push_back(i);
        a[e[i].y].push_back(i);
    }
    if(!pare())
        fout<<-1;
    else
    {
        rezolv(1);
        if ((int)ce.size() != m + 1)
            fout<<-1;
        else
        {
            for(auto y:ce)
            {
                fout<<y<<' ';
            }
        }
    }
    return 0;
}