Cod sursa(job #368278)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 24 noiembrie 2009 13:24:04
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <stack>
#include <list>
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
int N,M;
stack<int> st,rez;
list<int> G[100010];
int grad[100010];
int ok=1;

void citire(){
	fi>>N>>M;
	int x,y;
	for (int i=1;i<=M;++i){
		fi>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
		++grad[x];++grad[y];
	}
	for (int i=1;i<=N;++i) 
		if (grad[i]%2){ok=0;return ;}
	fi.close();
}

void euler(){
	st.push(1);
	while (!st.empty()){
		int nod=st.top();
		if (G[nod].empty()){
			rez.push(nod);
			st.pop();
		} else {
			st.push(*G[nod].begin());
			G[nod].pop_front();
			int x=st.top();
			list<int>::iterator end=G[x].end();
			for (list<int>::iterator it=G[x].begin();it!=end;++it)
				if (*it==nod) {
					G[x].erase(it);
					break ;
				}
		}
	}
	while (rez.size()>1) { fo<<rez.top()<<" "; rez.pop(); }
}

int main(){
	citire();
	if (ok) euler(); else fo<<"-1\n";
	fo.close();
	return 0;
}