Cod sursa(job #1364616)

Utilizator DarianCDarian Craciun DarianC Data 27 februarie 2015 19:06:07
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#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*5],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;
}