Cod sursa(job #2049445)

Utilizator rangal3Tudor Anastasiei rangal3 Data 27 octombrie 2017 10:36:36
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <vector>
#define file "ciclueuler"
#define N 100003

using namespace std;

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

struct nod{
    int info;
    nod *urm;
}*p[N],*u[N];

int n,m,x,y;
int gr[N];

bool Ciclu()
{
    for(int i=1; i<=n; ++i)
        if(gr[i] == 0 || gr[i]%2 != 0) return 0;
    return 1;
}

int sol[5*N],nsol;

inline void elim(const int &nod,const int &x)
{
    bool gasit = false;
    for(::nod *c = p[nod]; !gasit && c != NULL; c = c->urm)
        if(c->info == x)
        {
            gasit = true;
            c->info = -1;
        }
}

inline void Euler(int nod)
{
    ::nod *c = p[nod];
    for(; c != NULL; c = c->urm)
    {
        if(c->info == -1) continue;

        int nodurm = c->info;

        elim(c->info,nod);
        c->info = -1;

        Euler(nodurm);

        sol[++nsol] = nod;
    }
}

inline void add_nod(const int &x,const int &y)
{
    nod *c = new nod;
    c->urm = NULL;
    c->info = y;
    if(p[x]  == NULL)
        p[x] = u[x] = c;
    else
    {
        u[x]->urm = c;
        u[x] = c;
    }
}

void afisare()
{
    for(int i=1; i<=n; ++i)
    {
        fout<<i<<" : ";
        for(::nod *c = p[i]; c != NULL; c = c->urm)
            fout<<c->info<<" ";
        fout<<"\n";
    }
}

int main()
{

    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        add_nod(x,y);
        if(x != y)
            add_nod(y,x);
        ++gr[x];
        ++gr[y];
    }

    //afisare();

    if(Ciclu())
    {
        Euler(1);

        for(int i=1; i<=nsol; ++i)
            fout<<sol[i]<<" ";
    }
    else fout<<"-1\n";

    fin.close(); fout.close();
    return 0;
}