Cod sursa(job #1487428)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 16 septembrie 2015 20:06:48
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100005
using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

int m,n,x,y,deg[NMAX];
vector<int> a[NMAX],sol;

void citire()
{
    in >> n >> m;
    for(int i=0;i<m;i++)
    {
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
}

void euler()
{
    int aux,nod;
    stack<int> stiva;
    stiva.push(1);

    while(!stiva.empty())
    {
        nod = stiva.top();
        if(!a[nod].empty())
        {
            aux = a[nod].back();
            stiva.push(aux);
            a[nod].pop_back();
            //a[aux].erase(find(a[aux].begin(),a[aux].end(),nod));
            for(int i=0;i<a[aux].size();i++)
                if(a[aux][i]==nod)
            {
                a[aux].erase(a[aux].begin() + i);
                break;
            }

        }
        else
        {
           // out << nod << " ";
           sol.push_back(nod);
            stiva.pop();
        }
    }
}



int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(deg[i]%2!=0)
        {
            out << -1;
            return 0;
        }
    euler();
    sol.pop_back();
    for(int i=0;i<sol.size();i++)
        out << sol[i] << " ";
    return 0;
}