Cod sursa(job #3304932)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 28 iulie 2025 19:36:12
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
using namespace std;
struct muchie{
	int y, i;
};
int grad[100005], f[100005], is[100005], edges[500005];
vector <muchie> v[100005];
vector <int> ras;
void dfs1( int x ){
	int i, y;
	for( i = 0; i < v[x].size(); i++ ){
		y = v[x][i].y;
		if( f[y] == 0 ){
			f[y] = 1;
			dfs1( y );
		}
	}
}
void dfs2( int x ){
	int y, edge;
	while( is[x] < v[x].size() ){
		edge = v[x][is[x]].i;
		y = v[x][is[x]].y;
		is[x]++;
		if( edges[edge] == 0 ){
			edges[edge] = 1;
			dfs2( y );
		}
	}
	ras.push_back( x );
}
int main(){
	int n, m, i, x, y, ok;
	ifstream fin( "ciclueuler.in" );
	ofstream fout( "ciclueuler.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y;
		v[x].push_back( { y, i } );
		v[y].push_back( { x, i } );
		grad[x]++;
		grad[y]++;
	}
	f[1] = 1;
	dfs1( 1 );
	ok = i = 1;
	while( i <= n && ok == 1 ){
		if( f[i] == 0 || grad[i] % 2 == 1 ){
			ok = 0;
		}
		i++;
	}
	if( ok == 0 ){
		fout << -1;
	}
	else{
		dfs2( 1 );
		ras.pop_back();
		for( i = 0; i < ras.size(); i++ ){
			fout << ras[i] << ' ';
		}
	}
	return 0;
}