Cod sursa(job #927196)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 25 martie 2013 17:34:49
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <map>
using namespace std;

ifstream cin("ciclueuler.in"); ofstream cout("ciclueuler.out");

vector <int> rez;
int i, j, n, m, x, y, st, fn;
vector <int> v[100005];
map < pair<int, int>, int> mp;
int par[100005];

void dfs (int fx){
	vector <int> part;
	
	for (vector<int>::iterator it = v[fx].begin(); it!=v[fx].end(); it++){
		if (mp[make_pair(fx, (*it))]){
			mp[make_pair(fx, (*it))]--;
			mp[make_pair((*it), fx)]--;
			dfs(*it);
			rez.push_back(*it);
		}
	}

}

int main(){
	cin>>n>>m;
	for (i=1; i<=m; i++){
		cin>>x>>y;
		par[x]++; par[y]++;
		v[x].push_back(y);
		v[y].push_back(x);
		mp[make_pair(x, y)]++;
		mp[make_pair(y, x)]++;
	}
	
	for (i=1; i<=n; i++) if (par[i]%2){
		st=-1;
		break;
	}
	
	if (fn == -1) cout<<-1;
	else {
		dfs(1);
		for (vector<int>::iterator it = rez.begin(); it!=rez.end(); it++){
			cout<<(*it)<<" ";
		}
	}
}