Cod sursa(job #587281)

Utilizator rootsroots1 roots Data 4 mai 2011 16:07:14
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <string.h>
#include <vector>

#define MAX 1001

using namespace std;

int use[MAX],cnt[MAX],q[MAX],st[MAX],x[MAX],y[MAX];
vector <int> v[MAX];

int main()
{
    int M,N,i,ind,endst=0,endq=0,nod;

    ifstream in ("ciclueuler.in");

    in>>N>>M;
    for(i=1;i<=M;i++)
    {
        in>>x[i]>>y[i];
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }

    in.close();

    ofstream out ("ciclueuler.out");

    for(i=1;i<=N;i++)
        if(v[i].size()&1)
        {
            out<<-1<<'\n';

            out.close();

            return 0;
        }

    memset(q,0,sizeof(q));
    memset(st,0,sizeof(st));
    memset(cnt,0,sizeof(cnt));
    memset(use,0,sizeof(use));

    endst=1;
    st[endst]=1;

    while(endst)
    {
        nod=st[endst];
        while(cnt[nod]<v[nod].size()&&endst+endq!=M+1)
        {
            ind=v[nod][cnt[nod]++];
            if(!use[ind])
            {
                use[ind]=1;
                if(nod==x[ind])
                {
                    st[++endst]=y[ind];
                    nod=st[endst];
                }
                else
                {
                    st[++endst]=x[ind];
                    nod=st[endst];
                }
            }
        }
        q[++endq]=st[endst--];
    }

    for(i=1;i<endq-1;i++)
        out<<q[i]<<' ';
    out<<q[endq-1]<<'\n';

    out.close();
}