Cod sursa(job #1832695)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 20 decembrie 2016 18:59:33
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define NMax 100005

using namespace std;

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

int N,M;
vector<int> Graf[NMax],Sol;
stack<int> Stack;
bool mark[NMax];
int rang[NMax];

void Read();
void Write();

void Euler()
{
    Stack.push(1);
    while(!Stack.empty())
    {
        int nod=Stack.top();
        if(Graf[nod].size()==0)
        {
            Stack.pop();
            Sol.push_back(nod);
        }
        else
        {
            int to=Graf[nod][Graf[nod].size()-1];
            Graf[nod].pop_back();
            Stack.push(to);
            Graf[to].erase(find(Graf[to].begin(),Graf[to].end(),nod));
        }
    }
}

int main()
{
    Read();
    for(int i=1;i<=N;i++)
        if(rang[i]%2==1)
        {
            fout<<"-1";
            return 0;
        }
    Euler();
    Write();
    return 0;
}

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int from,to;
        fin>>from>>to;
        Graf[from].push_back(to);
        Graf[to].push_back(from);
        rang[from]++; rang[to]++;
    }
}

void Write()
{
    Sol.pop_back();
    for(vector<int>::iterator it=Sol.begin();it!=Sol.end();it++)
        fout<<*it<<" ";
}