Cod sursa(job #1014308)

Utilizator andreiiiiPopa Andrei andreiiii Data 22 octombrie 2013 13:55:43
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define N 100001
using namespace std;

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

vector <int> a[N], sol;
int s[N*10], sk;
int n, m;

void dfs(int x)
{
	int y;
	s[++sk]=x;
	while(sk)
	{
		x=s[sk];
		if(a[x].size())
		{
			y=a[x].back();
			a[x].pop_back();
			s[++sk]=y;
			a[y].erase(find(a[y].begin(), a[y].end(), x));
		}
		else
		{
			sk--;
			sol.push_back(x);
		}
	}
}

bool verif()
{
	for(int i=1;i<=n;i++)
	{
		if(a[i].size()%2) return 0;
	}
	return 1;
}

int main()
{
	int i, x, y;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	if(verif())
	{
		dfs(1);
		for(i=0;i<sol.size()-1;i++)
		{
			fout<<sol[i]<<" ";
		}
	}
	else fout<<-1;
}