Cod sursa(job #877745)

Utilizator raulstoinStoin Raul raulstoin Data 13 februarie 2013 09:37:33
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<vector>
#include<stack>
#define NMAX 100005
#define vec G[nod][i]
using namespace std;
int n,m,nr;
vector<int> G[NMAX];
bool use[NMAX];
stack<int> s,sol;
void read()
{
	freopen("ciclueuler.in","r",stdin);
	scanf("%d %d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}
void DFS(int nod)
{
	nr++;
	use[nod]=1;
	for(size_t i=0;i<G[nod].size();i++)
		if(!use[vec])
			DFS(vec);
}
bool is_euler()
{
	DFS(1);
	if(nr!=n)
		return 0;
	for(int i=1;i<=n;i++)
		if(G[i].size()%2)
			return 0;
	return 1;
}
void del(int x,int y)
{
	vector<int>::iterator it;
	for(it=G[x].begin();it!=G[x].end();it++)
		if(*it==y)
		{
			G[x].erase(it);
			return;
		}
}
void euler(int nod)
{
	int x;
	while(true)
	{
		if(G[nod].empty())
			return;
		x=G[nod].front();
		G[nod].erase(G[nod].begin());
		s.push(nod);
		del(x,nod);
		nod=x;
	}
}
void solve()
{
	freopen("ciclueuler.out","w",stdout);
	if(!is_euler())
	{
		printf("-1");
		return;
	}
	int x=1;
	do
	{
		euler(x);
		x=s.top();
		s.pop();
		sol.push(x);
	}while(!s.empty());
	while(!sol.empty())
	{
		printf("%d ",sol.top());
		sol.pop();
	}
}
int main()
{
	read();
	solve();
	return 0;
}