Cod sursa(job #1045589)

Utilizator Kira96Denis Mita Kira96 Data 1 decembrie 2013 19:19:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<vector>
#include<stack>
#define N 100100
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector< pair<int,int> >v[N];
pair<int,int> muchie;
stack<int> s;
int nod,n,m,i,x,y,gr[N],E[5*N],e;
bool used[5*N],viz[N];
void dfs(int x)
{
	viz[x]=1;
	for(int k=0;k<v[x].size();++k)
		if(!viz[v[x][k].first])
			dfs(v[x][k].first);
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		v[x].push_back(make_pair(y,i));
		v[y].push_back(make_pair(x,i));
		gr[x]++;
		gr[y]++;
	}
	for(i=1;i<=n;++i)
		if(!gr[i])
			viz[i]=1;
	for(i=1;i<=n;++i)
		if(gr[i])
		{
			dfs(i);
			break;
		}
	s.push(i);
	for(i=1;i<=n;++i)
		if((gr[i]%2)||(!viz[i]))
		{
			g<<"-1";
			return 0;
		}
	while(!s.empty())
	{
		nod=s.top();
		if(v[nod].empty())
		{
			E[++e]=nod;
			s.pop();
		}
		else
		{
			muchie=v[nod][v[nod].size()-1];
			if(used[muchie.second])
				v[nod].pop_back();
			else
			{
				used[muchie.second]=1;
				s.push(muchie.first);
			}
		}
	}
	for(i=1;i<e;++i)
		g<<E[i]<<" ";
	return 0;
}