Cod sursa(job #2562124)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 29 februarie 2020 12:23:36
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N=100001;
const int M=500001;

struct muchie
{
    int x, y;
    bool sters;
}vm[M];

int edg[2*M],urm[2*M],lst[N],nr,nc,ciclu[M];

void dfs (int nod)
{
    muchie e;
    int y;
    for (int p=lst[nod];p!=0;p=urm[p])
    {
        e=vm[edg[p]];
        if (e.sters) continue;
        y=e.x+e.y-nod;
        vm[edg[p]].sters=true;
        lst[nod]=urm[p];
        dfs (y);
    }
    ciclu[++nc]=nod;
}
int main()
{
    int n,m;
    in>>n>>m;
    for (int i=0;i<m;i++)
    {
        in>>vm[i].x>>vm[i].y;
        edg[++nr]=i;
        urm[nr]=lst[vm[i].x];
        lst[vm[i].x]=nr;
        edg[++nr]=i;
        urm[nr]=lst[vm[i].y];
        lst[vm[i].y]=nr;
    }
    dfs (1);
    /*for (int i=1;i<=nc;i++)
        cout<<ciclu[i]<<' ';*/
    if (nc==m+1)
        for (int i=1;i<nc;i++)
            out<<ciclu[i]<<' ';
    else out<<-1;
    return 0;
}