Cod sursa(job #1147607)

Utilizator SilverGSilver Gains SilverG Data 19 martie 2014 23:10:15
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
/*
    Keep It Simple!
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<stdio.h>
#include<list>
#include<stack>

#define MaxN 100001

using namespace std;

int N, M;
list<int> G[MaxN],Eu;
stack<int> Queue;
bool viz[MaxN];

void DFS(int node)
{
	viz[node] = 1;
	for (list<int>::iterator it = G[node].begin(); it != G[node].end(); it++)
	if (!viz[*it]) DFS(*it);
}

bool IsEulerian()
{
	for (int i = 1; i <= N;i++)
	  if (G[i].size() % 2)
		return 0;
	  DFS(1);
	  for (int i = 1; i <= N;i++)
	  if (!viz[i]) return 0;
	  return 1;
}

void DeleteRoads(int a, int b)
{
	G[a].pop_front();
	for (list<int>::iterator it = G[b].begin(); it != G[b].end(); it++)
	 if (*it == a)
	  { G[b].erase(it); break; }
}

void InitEulerian(int node)
{
	do
	{
		while (G[node].size())
		{
			int aux = G[node].front();
			DeleteRoads(node, aux);
			Queue.push(node);
			node = aux;
		}
		int val = Queue.top();
		Queue.pop();
		Eu.push_front(val);
		node = val;
	} while (Queue.size());
}

int main()
{
	freopen("elmaj.in", "r", stdin);
	freopen("elmaj.out", "w", stdout);

	scanf("%d%d", &N,&M);

	int x, y;

	for (int i = 1; i <= M; i++)
	{
		scanf("%d%d", &x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	if (IsEulerian())
	{
		InitEulerian(1);
		for (list<int>::iterator it = Eu.begin(); it != Eu.end(); it++)
			printf("%d ", *it);
	}
	else
		printf("-1");

	return 0;
}