Cod sursa(job #764140)

Utilizator SmarandaMaria Pandele Smaranda Data 4 iulie 2012 11:01:06
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <vector>
#include <list>
using namespace std;
vector <long> a[100001];
vector <long> :: iterator it;
list <long> q;
long e[500001];
bool viz[100001];
long  fleury (long &x) {
    long y;
    for (it=a[x].end()-1;it>=a[x].begin();--it) {
        if (viz[*it]==1) {
            y=*it;
            a[x].erase(it);
            return y;
        }
    }
    y=a[x].back();
    a[x].pop_back();
    return y;
}

int main () {
	long n,m,x,y,u=0,i;
	bool ok=1;

	freopen ("ciclueuler.in","r",stdin);
	freopen ("ciclueuler.out","w",stdout);

	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++) {
		scanf("%ld%ld",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (i=1;i<=n && ok;i++)
        if (a[i].size()%2)
            ok=0;
    if (ok==0)
        printf ("-1\n");
    else {
        q.push_back(1);
        viz[1]=1;
        while (!q.empty()) {
            x=q.front();
            if (a[x].empty()==1) {
                if (q.size()!=1)
                    printf("%ld ",x);
                q.pop_front();
            }
            else {
                y=fleury(x);
                q.push_front(y);
                viz[y]=1;
                for (it=a[y].begin();it!=a[y].end();++it)
                    if ((*it)==x) {
                        a[y].erase(it);
                        break;
                    }
            }
        }
        printf ("\n");
    }
	return 0;
}