Cod sursa(job #2735087)

Utilizator valeriucaraselCarasel Valeriu valeriucarasel Data 1 aprilie 2021 20:06:06
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int N=100005,M=500005;

vector<int> a[N],c;

struct muchie
{
    int x,y;
    bool anulat;
};
muchie e[M];

void euler(int x)
{
    for (int j=a[x].size()-1;j>=0;j--)
    {
        int i=a[x][j];
        a[x].pop_back();
        if (e[i].anulat) continue;
        int y=(x^e[i].x^e[i].y);
        e[i].anulat=true;
        euler(y);
    }
    c.push_back(x);
}

int vec[N+2];

int main()
{
    ifstream in("ciclueuler.in");
    ofstream out("ciclueuler.out");
    int n,m;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>e[i].x>>e[i].y;
        vec[e[i].x]++;
        vec[e[i].y]++;
        a[e[i].x].push_back(i);
        a[e[i].y].push_back(i);
    }
    for (int i=1;i<=n;i++)
    {
        if (vec[i]%2!=0)
        {
            out<<-1;
            return 0;
        }
    }
    euler(1);
    for (int i=0;i<c.size();i++)
    {
        out<<c[i]<<" ";
    }
    in.close();
    out.close();
    return 0;
}