Cod sursa(job #794996)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 7 octombrie 2012 14:21:20
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <stdio.h>
#include <queue>
#include <stack>
#include <list>
using namespace std;

list<int> G[100005];
int n,m;
int deg[100005];
queue<int> q;
int viz[100005];
	
stack<int> S;
list<int> L;	
bool eulerianAndConex(){
	int u;
	for(int i=1;i<=n;i++) if(deg[i]%2!=0) return false;
	q.push(1);viz[1]=1;
	while(!q.empty()){
		u=q.front();q.pop();
		for(list<int>::iterator it = G[u].begin();it!=G[u].end();it++)
		if(!viz[*it]){viz[*it]=1;q.push(*it);}
	}
	for(int i=1;i<=n;i++) if(!viz[i]) return false;
	return true;
}


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

void euler(int n){
	//S.push(n);
	int u=n,v;
	do
	{	
		while(true){
			if(G[u].empty()) break;
			v=G[u].front();
			eraseEdge(u,v);
			S.push(u);
			u=v;
		}
		u=S.top();S.pop();
		L.push_back(u);
	}while(!S.empty());
	
}

void euler2(int u){
	int v;
	while(!G[u].empty()){
		v=G[u].front();eraseEdge(u,v);
		euler2(v);
		L.push_back(u);
	}
}

int main(){
	int x,y;
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d",&x);scanf("%d",&y);
		G[x].push_back(y);G[y].push_back(x);
		deg[x]++;deg[y]++;
	}
	if(!eulerianAndConex()){printf("-1");return 0;}
	euler2(1);
	for(list<int>::iterator it = L.begin();it!=L.end();it++){
		printf("%d ",(*it));
	}
	return 0;
}