Cod sursa(job #474223)

Utilizator cosmyoPaunel Cosmin cosmyo Data 2 august 2010 22:33:13
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream.h>
#include<list>
#define NMAX 100005
#include<stack>
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
stack<long> st;
LI a[NMAX];
long nr,n,m,sol[600005];
void cit()
{ifstream fin("ciclueuler.in");
  fin>>n>>m;
  long i,x,y;
	  for(i=1;i<=m;++i)
	  {fin>>x>>y;
	  if(x!=y)
	  {a[x].push_back(y);
	   a[y].push_back(x);
	  }else
		  a[x].push_back(y);
	  }
 fin.close();
}
void dfs()
{long i,k;
 IT it,q;
 st.push(1);
	 while(!st.empty())
	 {k=st.top();
	  if(!a[k].empty())
		 {it=a[k].begin();
	      st.push(*it);
		  if(k!=*it)
		  {
		  for(q=a[*it].begin();q!=a[*it].end();++q)
			  if(*q==k)
				  break;
		  a[*it].erase(q);
		  }
		  a[k].erase(it);
		 }
		else
		{sol[++nr]=k;
		 st.pop();
		}
	 }
}
void afis()
{ofstream fout("ciclueuler.out");
 long i;
 if(sol[nr]!=sol[1])
	 fout<<-1;
 else
  for(i=1;i<=nr-1;++i)
	  fout<<sol[i]<<" ";
  fout<<'\n';
  fout.close();
}
int main()
{cit();
 dfs();
 afis();
 return 0;
}