Cod sursa(job #2345696)

Utilizator crion1999Anitei cristi crion1999 Data 16 februarie 2019 16:50:18
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
	
using namespace std;
	
 
	
int n, m;
	
 
	
vector<vector<pair<int, int> > > graph;
	
vector<int> cycle;
	
vector<bool> edge;
	
 
	
int main()
	
{
	
    ifstream fin("ciclueuler.in");
	
    ofstream fout("ciclueuler.out");
	
 
	
    fin>>n>>m;
	
 
	
    graph.resize(n+1, vector<pair<int, int> >());
	
    edge.resize(m+1, true);
	
 
	
    int x, y;
	
    for(auto i=1; i<=m; i++){
	
        fin>>x>>y;
	
        graph.at(x).push_back(make_pair(y, i));
	
        graph.at(y).push_back(make_pair(x, i));
	
    }
	
 
	
    for(size_t i=1; i<graph.size(); i++) if(graph.at(i).size()&1){
	
 
	
        fout<<-1;
	
        return 0;
	
    }
	
 
	
    stack<int> Stack;   Stack.push(1);
	
 
	
    while(!Stack.empty()){
	
        int current_node = Stack.top();
	
 
	
        if(!graph.at(current_node).empty()){
	
            int neighbour = graph.at(current_node).back().first;
	
            int Index = graph.at(current_node).back().second;
	
 
	
            graph.at(current_node).pop_back();
	
 
	
            if(edge.at(Index)==true){
	
                edge.at(Index) = false;
	
                Stack.push(neighbour);
	
            }
	
 
	
        } else {
	
            Stack.pop();
	
            cycle.push_back(current_node);
	
        }
	
    }
	
 
	
    cycle.pop_back();
	
    for(auto& elem:cycle) fout<<elem<<" ";