Cod sursa(job #1145996)

Utilizator vladrochianVlad Rochian vladrochian Data 18 martie 2014 17:02:51
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <list>
using namespace std;
#define fori(C) for(list<int>::iterator it=C.begin();it!=C.end();++it)
list<int> g[100001];
int n,m,s[500001],si;
bool v[100001];
void dfs(int nod)
{
	v[nod]=1;
	fori(g[nod])
		if(!v[*it])
			dfs(*it);
}
void euler(int nod)
{
	while(!g[nod].empty())
	{
		int vecin=g[nod].front();
    g[nod].pop_front();
		s[++si]=nod;
    fori(g[vecin])
			if(*it==nod)
			{
				g[vecin].erase(it);
				break;
			}
		nod=vecin;
	}
}
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int main()
{
	int x,y,nod;
	fin>>n>>m;
	while(m--)
	{
		fin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1);
	for(nod=1;nod<=n;++nod)
		if(!v[nod] || g[nod].size()&1)
		{
			fout<<"-1\n";
			return 0;
		}
	nod=1;
	do
	{
		euler(nod);
		nod=s[si--];
		fout<<nod<<" ";
	}while(si);
	return 0;
}