Cod sursa(job #755963)

Utilizator roxyroxy2011Luca Roxana roxyroxy2011 Data 8 iunie 2012 12:44:50
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#define NRMAX 100001

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int viz[NRMAX],n,m;
vector<int> lis[NRMAX];
stack<int> sol;

void read();
void conex();
void write();
void solve();
void dfs();

int main()
{
	read();
	conex();
	solve();
	write();
	f.close();g.close();
	return 0;
}

void read()
{
	f>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int l,c;f>>l>>c;
		lis[l].push_back(c);
		lis[c].push_back(l);
	}
}

void conex()
{
	dfs();
	for (int i=1;i<=n;i++)
		if (viz[i]==0 || lis[i].size()%2==1) 
		{g<<"-1"<<'\n';f.close();g.close();exit(0);}
}

void dfs()
{
	queue<int>que;
	que.push(1);
	while (!que.empty())
	{
		int aux=que.front();que.pop();
		for (int i=0;i<lis[aux].size();i++)
			if (viz[lis[aux][i]]==0)
			{
				viz[lis[aux][i]]=1;
				que.push(lis[aux][i]);
			}
	}
}

void solve()
{
	int aux=1,p=lis[1].back();
	while (p!=1)
	{
		sol.push(p);
		lis[aux].pop_back();
		for (int it=0;it<lis[p].size();it++)
		if (lis[p][it]==aux)
			{lis[p].erase(lis[p].begin()+it);break;}
		aux=p;p=lis[p].back();
	}
}

void write()
{
	g<<'1'<<' ';
	while (!sol.empty())
	{
		g<<sol.top()<<' ';
		sol.pop();
	}
	g<<'\n';
}