Cod sursa(job #2572080)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 5 martie 2020 11:32:09
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>
using namespace std;

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

const int N = 100000;
const int M = 500000;

vector <int> g[N+1];
vector <int> stiva;
vector <int> ciclu;
bool used[M];
int from[M], to[M];

void euler(int node){
	stiva.push_back(node);
	while(!stiva.empty()){
		node = stiva.back();
		if(!g[node].empty()){
			int edge = g[node].back();
			g[node].pop_back();
			if(!used[edge]){
				used[edge] = true;
				int next = to[edge];
				if(next == node)
					next = from[edge];
				stiva.push_back(next);
			}
		}
		else{
			ciclu.push_back(node);
			stiva.pop_back();
		}
	}
}

int main()
{
	int n,m,i,x,y,start;
	bool eulerian;
	fin >> n >> m;
	for(i=0; i<m; i++){
		fin >> x >> y;
		start = x;
		g[x].push_back(i);
		g[y].push_back(i);
		from[i] = x, to[i] = y;
	}
	eulerian = true;
	for(i=1; i<=n && eulerian; i++)
		if((int)g[i].size() % 2 == 1)
			eulerian = false;
	if(!eulerian)
		fout << "-1\n";
	else{
		euler(start);
		for(i=0; i<(int)ciclu.size() - 1; i++)
			fout << ciclu[i] << " ";
	}
	return 0;
}