Cod sursa(job #807992)

Utilizator RaduDoStochitoiu Radu RaduDo Data 6 noiembrie 2012 00:12:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>
#include <list>
#include <cstring>
#define pb push_back
#define MAXN 100010
using namespace std;
vector<int> G[MAXN];
list <int> Q;
int nc,nr,i,k,n,m,x,y,ev;
bool ok; 

void euler(int x)
{
	vector<int>::iterator it;
	Q.pb(x);
	while (!Q.empty())
	{
		x=Q.front();
		if(G[x].empty())
		{
			Q.pop_front();
			printf("%d ",x);
		}
		else
		{
			int i=G[x].back();
			Q.push_front(i);
			G[x].pop_back();
			for(it=G[i].begin();it!=G[i].end();++it)
				if(*it==x)
				{
					G[i].erase(it);
					break;
				}
		}
	}
}

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(; m>0; --m)
	{
		scanf("%d%d",&x,&y);
		G[x].pb(y);
		G[y].pb(x);
	}
	for(i=1;i<=n;++i)
		if(G[i].size()%2==1)
			{printf("-1\n");break;ev=1;}
	if(ev==0)
	{
		ev=1;
		for(i=1;i<=n&&ev;++i)
			if(G[i].size()%2==0)
				ev=0,euler(i);
		printf("\n");
	}
	return 0;
}