Cod sursa(job #1937724)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 24 martie 2017 10:28:53
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
using namespace std;
 
FILE*IN,*OUT;
 
int N,M,X,Y,fr[MaxN],Stack[5*MaxN],Size=0;
deque<pair<int,int> >Graph[MaxN];
bool found[5*MaxN];
void Euler(int node)
{
	Stack[++Size]=node;
	while(Size)
	{
		node=Stack[Size];
		while(!Graph[node].empty()&&found[Graph[node][0].second])
			Graph[node].pop_front();
		if(!Graph[node].empty())
		{
			Stack[++Size]=Graph[node][0].first;
			found[Graph[node][0].second]=true;
			Graph[node].pop_front();
		}
		else
		{
			if(Size>1)fprintf(OUT,"%d ",node);
			Size--;
		}
	}
}
int main()
{
    IN=fopen("ciclueuler.in","r");
    OUT=fopen("ciclueuler.out","w");
	
	fscanf(IN,"%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d%d",&X,&Y);
		Graph[X].push_back(make_pair(Y,i));
		Graph[Y].push_back(make_pair(X,i));
		fr[X]++,fr[Y]++;
	}
	bool pos=true;
	for(int i=1;i<=N;i++)
		if(fr[i]%2==1)
		{
			pos=false;
			break;
		}
	if(pos)
		Euler(1);
	else
		fprintf(OUT,"-1");
	return 0;
}