Cod sursa(job #392401)

Utilizator RobybrasovRobert Hangu Robybrasov Data 7 februarie 2010 14:37:53
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <list>
#define N 100005
#define M 500005

using namespace std;

list<int> L[N];
int grad[N],st[M];

int main()
{
    int n,m;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        grad[x]++; grad[y]++;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (int i=1; i<=n; i++)
        if (grad[i]&1)
        {
            printf("-1");

            return 0;
        }

    st[1]=1;
    int p=1;
    while (p)
    {
        if (!L[st[p]].empty())
        {
            //vecinul
            int vc=L[st[p]].front();

            //sterge muchia
            L[st[p]].pop_front();
            list<int>::iterator it;
            for (it=L[vc].begin(); it!=L[vc].end() && *it!=st[p]; it++);
            L[vc].erase(it);

            //adauga in stiva
            st[++p]=vc;
        }
        else
            printf("%d ",st[p--]);
    }

    return 0;
}