Cod sursa(job #610941)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 29 august 2011 20:26:09
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
vector<int> V[100010];
stack<int> Q;
void read(),solve(),DFS(int);
int n,m,a,b,viz[100010],i,eulerian(),sol[100010],j;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d",&a,&b);
		V[a].push_back(b);
		V[b].push_back(a);
	}
}
void solve()
{
	if(!eulerian())printf("-1");
	Q.push(1);
	for(;!Q.empty();)
	{
		a=Q.top();Q.pop();
		while(V[a].size())
		{
			vector<int>::iterator it=V[a].begin();b=*it;
			//Q.push_front(b);
			Q.push(a);
			for(vector<int>::iterator w=V[b].begin();w!=V[b].end();w++)
				if(*w==a){V[b].erase(w);break;}
			V[a].erase(it);
			a=b;
		}
		sol[++j]=a;
	}
	for(i=j;i>=2;i--)printf("%d ",sol[i]);
}
int eulerian()
{
	memset(viz,0,sizeof(viz));
	DFS(1);viz[1]=1;
	for(i=1;i<=n;i++)
		if(!viz[i]||V[i].size()%2)return 0;
	return 1;
}
void DFS(int X)
{
	for(vector<int>::iterator it=V[X].begin();it!=V[X].end();it++)
		if(!viz[*it]){viz[*it]=1;DFS(*it);}
}