Cod sursa(job #493861)

Utilizator klamathixMihai Calancea klamathix Data 19 octombrie 2010 19:04:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
const int maxn = 100005;
using namespace std;

vector <int> G[maxn] , Sol;
stack <int> St;
queue <int> Q;

int i , n , m , a , b , dg[maxn];
bool seen[maxn];

bool BF() {
	int i , v;
	for ( Q.push(1) , seen[1] = true ; !Q.empty() ; ) {
		v = Q.front(); Q.pop();
		seen[v] = true;
		for( typeof(G[v].begin()) it = G[v].begin() ; it != G[v].end() ; ++it )
			if ( !seen[*it] ) Q.push(*it);
	}
	for( i = 1 ; i <= n ; ++i )
		if ( !seen[i] ) return false;
return true;
}	

bool ok() {
	for ( int i = 1 ; i <= n ; ++i )
		if ( dg[i] & 1 ) return false;
	return true;
}

void delete_edge(int v, int w) {
	G[v].pop_back();
	for( typeof(G[w].begin()) it = G[w].begin(); it != G[w].end() ; ++it)
		if ( *it == v ) {
			G[w].erase(it);
			return;
		}
}

void euler(int v)
{
	int w;
	while ( true ) {
		if ( G[v].empty() ) break;
		w = G[v].back();
		St.push(v);
		delete_edge (v , w);
		v = w;
	}
}

void ECycle()
{
	if ( !ok() ) {
		printf("-1\n");
		return;
	}
	
	int v = 1;
	do
	{
		euler(v);
		v = St.top() , St.pop();
		Sol.push_back(v);
	} while (! St.empty());
	
	for( i = 0 ; i < Sol.size() ; ++i)
		printf("%d ",Sol[i]);
}

int main()
{
	freopen("ciclueuler.in","r",stdin);
	freopen("ciclueuler.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( i = 1 ; i <= m ; ++i ) {
		scanf("%d %d",&a,&b);
		G[a].push_back(b), dg[a]++;
		G[b].push_back(a), dg[b]++;
	}
	
	ECycle();
return 0;
}