Cod sursa(job #2562122)

Utilizator DanSDan Teodor Savastre DanS Data 29 februarie 2020 12:23:22
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

int n, m, nr, nc, lst[N], urm[2*M], edges[2*M], ciclu[M];

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

void euler(int x)
{
    muchie e;
    int y;
    for(int p = lst[x]; p != 0; p = urm[p])
    {
        e = vm[edges[p]];
        if(e.sters) continue;
        y = e.x + e.y - x;
        vm[edges[p]].sters = true;
        lst[x] = urm[p];
        euler(y);
    }
    ciclu[++nc] = x;
}

int main()
{
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        in>>vm[i].x>>vm[i].y;

        edges[++nr] = i;
        urm[nr] = lst[vm[i].x];
        lst[vm[i].x] = nr;

        edges[++nr] = i;
        urm[nr] = lst[vm[i].y];
        lst[vm[i].y] = nr;
    }

    euler(1);

    if(nc != m+1)
    {
        out<<"-1";
        return 0;
    }
    for(int i=1; i<nc; i++)
    {
        out<<ciclu[i]<<' ';
    }
    return 0;
}