Cod sursa(job #1130087)

Utilizator raulstoinStoin Raul raulstoin Data 28 februarie 2014 11:16:16
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<vector>
#include<stack>
#include<cstring>

#define NMAX 100005

using namespace std;

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

int n,m;
vector<int> G[NMAX],sol;
stack<int> S;
bool use[NMAX];

void read()
{
	fin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void DFS(int nod)
{
	use[nod]=1;
	for(size_t i=0;i<G[nod].size();i++)
		if(!use[G[nod][i]])
			DFS(G[nod][i]);
}

bool Euler()
{
	DFS(1);
	for(int i=1;i<=n;i++)
		if(G[i].size()%2 || !use[i])
			return 0;
	memset(use,0,sizeof use);
	S.push(1);
	while(!S.empty())
	{
		int nod=S.top(),vec;
		if(G[nod].empty())
		{
			sol.push_back(S.top());
			S.pop();
			continue;
		}
		vec=G[nod].back();
		G[nod].pop_back();
		for(vector<int>::iterator it=G[vec].begin();it!=G[vec].end();++it)
			if(*it==nod)
			{
				G[vec].erase(it);
				break;
			}
		S.push(vec);
	}
	return 1;
}

int main()
{
	read();
	if(!Euler())
	{
		fout<<"-1";
		return 0;
	}
	for(size_t i=0;i<sol.size()-1;i++)
		fout<<sol[i]<<' ';
	return 0;
}