Cod sursa(job #2817736)

Utilizator OrzataAndreiOrzata Andrei OrzataAndrei Data 14 decembrie 2021 02:54:35
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN=100001;

int N,M,i,x,y;
vector<int> G[MAXN],ANS;

void elimin(int x,int edge)
{
    G[edge].pop_back();
    vector<int>::iterator it;
    for (it=G[x].begin(); it!=G[x].end(); it++)
        if (*it==edge)
        {
            G[x].erase(it);
            return;
        }
}

void ciclueuler()
{
    int x, edge = 1;

    stack<int> Stack;

    Stack.push(1);
    while (!Stack.empty())
    {

        edge=Stack.top();
        if (G[edge].empty())
        {
            ANS.push_back(edge);
            Stack.pop();
        }
        else
        {
            x=G[edge].back();
            elimin(x,edge);

            Stack.push(x);
        }
    }

}
int main()
{

    in>>N>>M;
    while (M--)
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i=1; i<=N; i++)
        if (G[i].size()%2 == 1)
        {
            out<<"-1\n";
            return 0;
        }

    ciclueuler();
    ANS.pop_back();
    for (i = 0; i < ANS.size(); i++)
        out<<ANS[i]<<' ';

    return 0;

}