Cod sursa(job #1141145)

Utilizator assa98Andrei Stanciu assa98 Data 12 martie 2014 17:33:23
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int MAX_N=100100;

vector<int> A[MAX_N];
bool viz[MAX_N];

void dfs(int nod) {
    viz[nod]=true;
    for(auto it=A[nod].begin(); it!=A[nod].end(); it++) {
        if(!viz[*it]) {
            dfs(*it);
        }
    }
}


bool ok(int n) {
    dfs(1);
    for(int i=1;i<=n;i++) {
            if(!viz[i]||A[i].size()%2) {
                return false;
            }
    }
    return true;
}

void sterge(int a,int b) {
    A[a].pop_back();
    for(auto it=A[b].begin(); it!=A[b].end(); it++) {
        if(*it==a) {
            A[b].erase(it);
            return;
        }
    }
}

vector<int> E;

void euler(int nod) {
    while(A[nod].size()) {
        int f=A[nod].back();
        sterge(nod,f);
        euler(f);
    }
    E.push_back(nod);
}

int main() {
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++) {
        int a,b;
        fin>>a>>b;
        A[a].push_back(b);
        A[b].push_back(a);
    }
    
    if(!ok(n)) {
        fout<<-1;
        return 0;
    }

    euler(1);
    
    for(auto it=E.begin(); it<E.end()-1;it++) {
        fout<<*it<<' ';
    }

    return 0;
}