Cod sursa(job #2171899)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 15 martie 2018 14:02:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
std::ifstream in("ciclueuler.in");
std::ofstream out("ciclueuler.out");
using namespace std;
const int max_nodes=100001;
const int max_edges=500001;
int grade[max_nodes];
struct elem
{
    int nod , nr;
};

vector<elem>G[max_nodes]; // graph
vector<int>answer;
stack<int>s;
bool viz[max_edges];
int n ,m;
inline void input()
{ int c=0;
    in>> n >> m ;
    for(int i =1 ; i <=m ;++i )
    {
        ++c;
        int a,b,cc;
        in >> a >> b ;
        grade[a]++, grade[b]++;
        elem w; w.nod=b,w.nr=c;
        G[a].push_back(w);
        w.nod=a;
        G[b].push_back(w);
    }
}

void euler_construnct()
{
    s.push(1);
    while(s.empty()==false)
    {
        int nod = s.top();
       if(G[nod].size())
       {
           int vecin = G[nod].back().nod;
           int muchie = G[nod].back().nr;

           G[nod].pop_back();

           if(!viz[muchie])
           {
               s.push(vecin);
               viz[muchie]=true;
           }
       }
       else
       {
           answer.push_back(nod);
           s.pop();
       }
    }
}


int main()
{
input();
for(int i =1; i<=n ;++i)
if(grade[i]&1){out<<"-1";return 0;}
euler_construnct();
for(int j = 0 ; j < answer.size()-1;++j)
    out<<answer[j]<<" ";


    return 0;
}