Cod sursa(job #734569)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 14 aprilie 2012 15:58:58
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
ofstream g("ciclueuler.out");
vector<int> a[100010];
vector<int>::iterator it;
deque<int> q;
int n,m,i,x,y,ok;
void euler(int nd)
{ int nod,nod2;
	q.push_front(nd);
	while(!q.empty())
	{
		nod=q.front();
		if(a[nod].size()==0)
		{
			g<<nod<<" ";
			q.pop_front();
			continue;
		}
	   nod2=a[nod].back();
	   a[nod].pop_back();
	   q.push_front(nod2);
	  for(it=a[nod2].begin();it!=a[nod2].end();it++)
	  if(*it==nod)
	  {
		  a[nod2].erase(it);
		  break;
	  }
	}
}
int main()
{
	ifstream f("ciclueuler.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
    }
	ok=1;
	for(i=1;i<=n;i++) if(a[i].size()%2){ ok=0; break;} 
	
	if(!ok)g<<-1<<"\n";
	 else  euler(1);
	f.close();g.close();
return 0;}