Cod sursa(job #1364641)

Utilizator DarianCDarian Craciun DarianC Data 27 februarie 2015 19:18:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<stack>
#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;
stack <int> S;
int 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)
{
    S.push(node);
    while(!S.empty())
    {
        x = S.top();
        if(a[x].size())
        {
            y = a[x].back();
            S.push(y);

            a[x].pop_back();
            a[y].erase( find(a[y].begin(), a[y].end(), x) );
        }
        else
            { sol.pb(S.top()); S.pop(); }
    }
}

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;
}