Cod sursa(job #906136)

Utilizator OpportunityVlad Negura Opportunity Data 6 martie 2013 15:36:58
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");

vector <int> G[100001],L;
long viz[100001],deg[100001],n,m,i;
queue <int> S;

void read(){
	int x,y;
	fi >> n >> m;
	for (i=1; i<=m; i++){
		fi >> x >> y;
		G[x].push_back(y); deg[x]++;
		G[y].push_back(x); deg[y]++;
	}
}

void bfs(int nod){
	queue <int> Q;
	Q.push(nod); viz[nod]=1;
	while (!Q.empty()){
		nod=Q.front(); Q.pop();
		vector <int>::iterator it;
		for (it=G[nod].begin(); it!=G[nod].end(); it++) 
			if (!viz[*it]) {
				viz[*it]=1;
				Q.push(*it);
			}
	}
}

int conex(){
	bfs(1);
	for (i=1; i<=n; i++)
		if (!viz[i]) return 0;
	return 1;
}

int eulerian(){
	if(!conex()) return 0;
	for (i=1; i<=n; i++) 
		if (deg[i]%2) return 0;
	return 1;
}

void sterge(int v,int w){
	deg[v]--,deg[w]--;
	G[v].pop_back();
	vector <int>::iterator it;
	for (it=G[w].begin(); it!=G[w].end(); it++)
		if (*it==v){
			G[w].erase(it);
			break;
		}
}

void euler(int v){
	while (!G[v].empty()){
		int w=G[v].back();
		S.push(v);
		sterge(v,w);
		v=w;
	}
}

int rez(){
	if (!eulerian()) return 0;
	int v=1;
	do {
		euler(v);
		v=S.front(); S.pop();
		L.push_back(v);
	}while (!S.empty());
	
	return 1;
}

void write(int v){
	if (!v) fo << "-1\n";
	vector <int>::iterator it;
	for (it=L.begin(); it!=L.end(); it++)
		fo << *it << " ";
}

int main(){
	
	read();
	write(rez());
	
	return 0;
}