Cod sursa(job #1060842)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 18 decembrie 2013 20:20:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=100005;
const int MAXM=500005;
int n,m;
int grad[MAXN];
vector<int> adj[MAXN],e;
stack<int> s;
bool is_eulerian()
{
	for (int i=1; i<=n; ++i)
	{
		if (grad[i]%2)
			return false;
	}
	return true;
}
void del_edge(int u,int v)
{
	//delete edge from u
	adj[u].pop_back();

	//delete edge from v
	for (vector<int>::iterator i=adj[v].begin(); i!=adj[v].end(); ++i)
	{
		if ((*i)==u)
		{
			adj[v].erase(i);
			break;
		}
	}
}
void euler_cycle()
{
	int u=0,v=0;
	s.push(1);
	while (!s.empty())
	{
		u=s.top();
		if (!adj[u].empty())
		{
			v=adj[u].back();
			s.push(v);
			del_edge(u,v);
		}
		else
		{
			s.pop();
			e.push_back(u);
		}
	}
}
int main()
{
	int k,x,y;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (k=1; k<=m; ++k)
	{
		scanf("%d%d",&x,&y);
		++grad[x];
		++grad[y];
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	if (is_eulerian())
	{
		euler_cycle();
		for (vector<int>::iterator i=e.begin(); i!=e.end(); ++i)
			printf("%d ",*i);
		printf("\n");
	}
	else
	{
		printf("-1\n");
	}
	return 0;
}