Cod sursa(job #601705)

Utilizator mihai995mihai995 mihai995 Data 7 iulie 2011 15:16:45
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;

const int N=100005,inf=1<<30;
int el[5*N],poz[5*N],n;
vector<int> a[N],P[N];

ifstream in("ciclueuler.in");

inline void push(int x,int y)
{
    a[x].push_back(y);
    P[x].push_back(a[y].size());
    P[y].push_back(a[x].size()-1);
    a[y].push_back(x);
}

inline void pop(int x,int y,int p)
{
    a[x][p]=a[y][P[x][p]]=-1;
}

void go(int &x,int &i)
{
    el[0]--;
    for (;i<a[x].size() && a[x][i]==-1;i++);
    if (i<a[x].size() && a[x][i]!=-1)
    {
        el[0]++;
        el[++el[0]]=a[x][i];
        poz[el[0]]=0;
        pop(x,a[x][i],i);
    }
    else
        printf("%d ",x);
    i++;
}

void euler(int x)
{
    el[++el[0]]=x;
    poz[el[0]]=0;
    while (el[0])
        go(el[el[0]],poz[el[0]]);
}

int main()
{
    freopen("ciclueuler.out","w",stdout);
    int m,x,y,i;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y;
        push(x,y);
    }
    for (i=1;i<=n;i++)
        if (a[i].size() & 1)
        {
            printf("-1\n");
            return 0;
        }
    euler(1);
    printf("\n");
    return 0;
}