Cod sursa(job #328272)

Utilizator zbarniZajzon Barna zbarni Data 1 iulie 2009 14:37:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <queue>
#include <list>
#include <stack>
#include <vector>
#define pb push_back
#define nx 100005
using namespace std;
vector <int> G[nx];
list <int> L;
stack <int> St;
int gr[nx],N,M;

int conex()
{
	queue <int> Q;
	int viz[nx]={0},nr=1;viz[1]=1;
	vector <int> :: iterator it;
	for (Q.push(1);!Q.empty();Q.pop())
	{
		int r=Q.front();
		for (it=G[r].begin();it!=G[r].end();++it)		
			if (!viz[*it])
			{
				Q.push(*it);
				viz[*it]=1;
				nr++;
			}
	}
	if (nr<N)	return 0;
	return 1;
}

int imp()
{
	for (int i=1;i<=N;++i)
		if (gr[i]%2)
			return 0;
	return 1;
}

void euler (int p)
{
	vector <int> :: iterator it,it2;
	while (1)	{
	for (it=G[p].begin();it!=G[p].end() && *it==0 ;++it)
	{	;	}
	if (it==G[p].end())	break;
	St.push(p);	
	for (it2=G[*it].begin();it2!=G[*it].end();++it2)
		if (*it2==p)
		{
			*it2=0;
			break;
		}
	if (*it==0) it++;
	gr[p]--,gr[*it]--;
	p=*it;
	*it=0;
	}
}

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%d%d",&x,&y);
		gr[x]++,gr[y]++;
		G[x].pb(y);
		G[y].pb(x);
	}
	if (!conex() || !imp())
	{
		printf("-1\n");
		return 0;
	}
	int p=1;
	do 
	{
		euler(p);
		p=St.top();
		St.pop();
		L.pb(p);
	}	while (!St.empty());
	list <int> :: iterator it;
	for (it=L.begin();it!=L.end();++it)
		printf("%d ",*it);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}