Cod sursa(job #734565)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 14 aprilie 2012 15:54:13
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<deque>
#include<vector>
using namespace std;
FILE *g=fopen("ciclueuler.out","w");

int i,j,n,m,x,y;
vector<int> a[100010];
vector<int>::iterator it;
deque<int> q;
void euler(int x)
{
	int nod,nod2;
	q.push_front(x);
	while(!q.empty())
	{
		nod=q.front();
		if(a[nod].size()==0)
		{
			fprintf(g,"%d ",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()
{
	FILE *f=fopen("ciclueuler.in","r");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	int ok=1;
	for(i=1;i<=n&&ok;++i)
		if(a[i].size()%2)
			ok=0;
		if(ok)
			euler(1);
		else
			fprintf(g,"-1\n");
		return 0;
}