Cod sursa(job #940560)

Utilizator costyv87Vlad Costin costyv87 Data 16 aprilie 2013 17:16:26
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cstdio>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <fstream>
#include <stack>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (a[(i)][(j)].c-a[(i)][(j)].f)
using namespace std;
list <int> a[100100];
bool bf[100100];
int gr[100100];
stack <int> S;
vector <int> sol;
int n,m;

void read()
{
    int i,x,y;

    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
}

void df(int x)
{
    bf[x]=true;
    for (list<int>::iterator i=a[x].begin();i!=a[x].end();i++) if (!bf[*i]) df(*i);
}

bool pre()
{
    df(1);
    for (int i=1;i<=n;i++) if (!bf[i] || gr[i]%2==1) return false;
    return true;
}

void euler(int x)
{
    int y;


    while (a[x].size()>0)
    {
        y=a[x].front();
        a[x].pop_front();
        for (list<int>::iterator j =a[y].begin();j!=a[y].end();j++)
            if (*j==x)
            {
                a[y].erase(j);
                break;
            }

        S.push(x);
        x=y;
    }
}

void solve()
{
    int x=1;

    do
    {
        euler(x);
        x=S.top(); S.pop();
        sol.push_back(x);
    }
    while (S.size());
    for (int i=0;i<sol.size();i++) printf("%d ",sol[i]);
}


int main()
{
    freopen( "ciclueuler.in", "r", stdin );
    freopen( "ciclueuler.out", "w", stdout );
    read();
    if (!pre()) { printf("-1"); return 0;}
    solve();

    return 0;
}