Cod sursa(job #2681284)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 5 decembrie 2020 11:15:39
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#include <stack>

using namespace std;

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

int n, m;
multiset<int> gra[100041];
int grad[100041];

int nxt = 0;
stack<int> sta;

void stakoneta(){
	sta.push(1);
	
	while(!sta.empty()){
		int a = sta.top();
		
		if(!gra[a].empty()){
			int b = *gra[a].begin();
			gra[a].erase(gra[a].begin());
			gra[b].erase(gra[b].find(a));
			sta.push(b);
		}else{
			sta.pop();
			if(nxt != 0)fout << nxt << " ";
			nxt = a;
		}
		
	}
}

int main(){
	// ios_base::sync_with_stdio(false);
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b;fin>> a >> b;
		gra[a].insert(b);grad[a]++;
		gra[b].insert(a);grad[b]++;
	}
	
	bool ok = true;;
	for(int i = 1; i <= n; ++i){
		if(grad[i]%2 != 0){
			ok = false;
			break;
		}
	}
	
	if(ok)stakoneta();
	else fout << -1;
	return 0;
}