Cod sursa(job #596684)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 18 iunie 2011 13:45:41
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define NMAX 100005
#define LMAX 500005
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
vector <pii> A[NMAX];
stack <int> st;
vector <int> sol;
int n,m,B[NMAX];
char viz[LMAX];
int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,x,y,nod;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		nod=x;
		A[x].pb(mp(i,y));
		A[y].pb(mp(i,x));
	}
	for (i=1; i<=n; i++)
		if (A[i].size() & 1)
		{
			printf("-1\n");
			return 0;
		}
	st.push(nod);
	int edge,act,find;
	while (!st.empty())
	{
		nod=st.top(); find=0;
		for (i=B[nod]; i<A[nod].size(); i++)
		{
			edge=A[nod][i].f; act=A[nod][i].s;
			if (!viz[edge])
			{
				viz[edge]=1; find=1;
				st.push(act);
				B[nod]=i+1;
				break ;
			}
		}
		if (!find)
		{
			sol.pb(st.top());
			st.pop();
		}
	}
	if (sol.size()!=m+1)
	{
		printf("-1\n");
		return 0;
	}
	for (i=sol.size()-1; i>0; i--)
		printf("%d ",sol[i]);
	printf("\n");
	return 0;
}