Cod sursa(job #1363861)

Utilizator DarianCDarian Craciun DarianC Data 27 februarie 2015 12:04:08
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
#define nmax 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector <int> a[nmax],sol;
int st[nmax],top,x,y,n,m;

bool Condition()
{
    for(int i=1;i<=n;i++)
        if(a[i].size()%2==1) return false;
    return true;
}
void Read()
{
    int i,j;
    fin>>n>>m;
    while(m--)
    {
        fin>>i>>j;
        a[i].pb(j);
        a[j].pb(i);
    }
    fin.close();
}

void Eulerian_Path(int node)
{
    st[++top] = node;
    while(top)
    {
        x = st[top];
        if(a[x].size())
        {
            y = a[x].back();
            a[x].pop_back();

            st[++top] = y;

            a[y].erase( find(a[y].begin(), a[y].end(), x) );
        }
        else
         sol.pb(st[top--]);
    }
}

void Print()
{
    for(unsigned int i = 0; i < sol.size()-1; i++)
        fout<<sol[i]<<' ';
   // fout<<'\n';
    fout.close();
}

int main()
{
    Read();
    if(!Condition())
        fout<<"-1";
    else
    {
        Eulerian_Path(1);
        Print();
    }
    return 0;
}