Cod sursa(job #368232)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 24 noiembrie 2009 11:06:12
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
vector<int> viz;
vector<pair<int,int> > rel[100010];
int rez[500010],vf,N,M,nr;
pair<int,unsigned int> st[500010];

void citire(){
	fi>>N>>M;
	int x,y;
	for (int i=1;i<=M;++i){
		fi>>x>>y;
		rel[x].push_back(make_pair(y,i-1));
		rel[y].push_back(make_pair(x,i-1));
		viz.push_back(0);
	}
	fi.close();
}

void euler(){
	vf=1;
	st[vf].first=1;
	st[vf].second=0;
	while (vf){
		if (st[vf].second>=rel[st[vf].first].size()){
			rez[++nr]=st[vf].first;
			--vf;
		} else if (viz[rel[st[vf].first][st[vf].second].second]==0){
			viz[rel[st[vf].first][st[vf].second].second]=1;
			++vf;
			st[vf].first=rel[st[vf-1].first][st[vf-1].second].first;
			st[vf].second=0;
		} else ++st[vf].second;
	}
}


int main(){
	citire();
	nr=0;
	euler();
	for (int i=2;i<nr;++i) fo<<rez[i]<<" ";
	fo<<rez[nr]<<"\n";
	fo.close();
	return 0;
}