Cod sursa(job #1536466)

Utilizator vasica38Vasile Catana vasica38 Data 26 noiembrie 2015 11:03:27
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>

using namespace std;

typedef struct lista
{
    int info;
    lista * next;
} * nod;

nod a[100123];

int i,j,k,m,n,u;
int grad[100123];
int st[500123];
int sol[500123];
void add (int x, nod &p)
{
    nod r = new lista;
    r->info=x;
    r->next=p;
    p=r;
}
int nr;
void ciclu()
{
    st[++u]=1;
    while (u)
    {
        if (!a[st[u]]) sol[++nr]=st[u--];
        else
        {
            int nd=st[u];
            int ndp=a[st[u]]->info;
            a[st[u]]=a[st[u]]->next;
            st[++u]=ndp;
            if (a[ndp]->info==nd) a[ndp]=a[ndp]->next;
                else
                {
                    nod r=a[ndp];
                    while (r->next)
                    {
                        if (r->next->info==nd)
                        {
                        r->next=r->next->next;
                        break;
                        }
                    r=r->next;
                    }
                }
        }
    }
}

int main()
{
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");
    cin>>n>>m;
    while (m--)
    {
        int x,y;
        cin>>x>>y;
        add(x,a[y]);
        add(y,a[x]);
        grad[x]++;
        grad[y]++;
    }
    for (i=1; i<=n; ++i)
    if (grad[i]%2) {cout<<-1; return 0;}
    ciclu();
    for (i=1; i<=nr-1; ++i) cout<<sol[i]<<" ";
    return 0;
}