Cod sursa(job #1521875)

Utilizator asavoaeigeoAsavoaei Georgiana asavoaeigeo Data 10 noiembrie 2015 22:06:53
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m, viz[100005],grad[100005],t[100005];
struct nod
{
    int info;
    nod *urm;
} *a[100005];
 
void Add(nod *&prim,int x)
{
    nod *p=new nod;
    p->info=x;
    p->urm=prim;
    prim=p;
}

void Citire()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
       fin>>x>>y;
       ++grad[x];
       ++grad[y];
       Add(a[x],y);
       Add(a[y],x); 
    }
}
int sol;
void DFS(int x)
{
    viz[x]=1;
    for(nod*p=a[x];p!=NULL;p=p->urm) 
     if(viz[p->info]==0) {t[p->info]=x; DFS(p->info);}
     else if(t[x]!=p->info) sol=p->info;
}



int Verificare()
{
    for(int i=1;i<=n;i++)
    if(grad[i]%2==1) return 0;
    DFS(1);
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0 && grad[i]!=0) return 0;
    }
    return 1;
}

void Ciclu(int y)
{
    if(t[y]!=0) Ciclu(t[y]);
    fout<<y<<" ";
}

int main()
{
    Citire();
    if(Verificare()==0) fout<<-1;
    else Ciclu(sol);
    return 0;
}