Cod sursa(job #610885)

Utilizator mihai995mihai995 mihai995 Data 29 august 2011 16:20:18
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;

const int N=100005,inf=1<<30;
int el[5*N],n;
struct leg{int y,poz;};
vector<leg> a[N];

ifstream in("ciclueuler.in");

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

inline void pop(vector<leg> &v,int p)
{
    a[v[p].y][v[p].poz].y=-1;
    v.resize(p);

}

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

void euler(int x)
{
    el[++el[0]]=x;
    while (el[0])
        go(a[el[el[0]]],el[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;
}