Cod sursa(job #3170921)

Utilizator alexioana_2006Apostolache Alexia alexioana_2006 Data 18 noiembrie 2023 11:15:59
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=500005;

struct muchii
{
    int st, dr, ind;
};

vector<muchii> M[nmax];

vector<int> V;

int n, m, fr[nmax],x,y;

void Euler(int x)
{
    while(M[x].size())
    {
        muchii k=M[x].back();

        M[x].pop_back();

        if(!fr[k.ind])
        {
            fr[k.ind]=1;
            Euler(k.dr);
        }
    }

    V.push_back(x);
}
int main()
{

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;

        M[x].push_back({x, y, i});
        M[y].push_back({y, x, i});
    }

    for(int i=1;i<=n;i++)

        if(M[i].size()%2==1)
        {
            fout<<-1;
            return 0;
        }

    Euler(1);

    for(int i=0;i<V.size()-1;i++)
        fout<<V[i]<<" ";

    return 0;
}