Cod sursa(job #694566)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 27 februarie 2012 21:49:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<cstdio>
#include<list>
#include<stack>
#include<bitset>

using namespace std;

#define Nmax 100001

list<int> G[Nmax], sol;
stack<int> S;
bitset<Nmax> use;
int N, M, grad[Nmax], ok(1);

void DF(int nod) {
    use[nod]=1;
    for(list<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
        if(!use[*it])
            DF(*it);
}

void sterge(int nod, int nod_vecin) {
    grad[nod]--;
    grad[nod_vecin]--;
    G[nod].pop_front();
    for(list<int>:: iterator it=G[nod_vecin].begin(); it!=G[nod_vecin].end(); ++it)
        if(*it==nod) {
            G[nod_vecin].erase(it);
            break;
        }
}

void euler(int nod) {
    while(1) {
        if(G[nod].empty()==true)
            break;
        S.push(nod);
        int nod_vecin=G[nod].front();
        sterge(nod,nod_vecin);
        nod=nod_vecin;
    }
}

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

    int i, j, nod;

    scanf("%d %d",&N,&M);
    while(M--) {
        scanf("%d %d",&i,&j);
        G[i].push_back(j);
        G[j].push_back(i);
        grad[i]++;
        grad[j]++;
    }
    for(i=1; i<=N; i++)
        if(grad[i]%2==1) {
            ok=0;
            break;
        }
    if(ok) {
        DF(1);
        for(i=1; i<=N; i++)
            if(!use[i]) {
                ok=0;
                break;
            }
    }
    if(!ok) {
        printf("-1\n");
        return 0;
    }
    nod=1;
    do {
        euler(nod);
        nod=S.top();
        S.pop();
        sol.push_back(nod);
    } while(!S.empty());

    for(list<int>:: iterator it=sol.begin(); it!=sol.end(); ++it)
        printf("%d ",*it);

    return 0;
}