Cod sursa(job #1689841)

Utilizator razvandRazvan Dumitru razvand Data 14 aprilie 2016 16:43:50
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100003

using namespace std;

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

vector<int> vec[MAX];
vector<int> ciclu;

void del(int a, int b) {
    for(vector<int>::iterator it = vec[a].begin(); it != vec[a].end(); it++) {
        if(*it == b) {
            vec[a].erase(it);
            return;
        }
    }
}

void euler() {

    stack<int> st;
    st.push(1);
    vector<int>::iterator it;
    int nod;
    int nxt;

    while(!st.empty()) {
        nod = st.top();
        if(vec[nod].size() != 0) {
            nxt = vec[nod].back();
            vec[nod].pop_back();
            del(nxt, nod);
            st.push(nxt);
        } else {
            ciclu.push_back(nod);
            st.pop();
        }
    }

}

int main() {

    int n,m,a,b;
    in >> n >> m;

    for(int i = 1; i <= m; i++) {
        in >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        if(vec[i].size()%2 != 0) {
            out << "-1";
            return 0;
        }
    }

    euler();

    for(vector<int>::iterator it = ciclu.begin(); it != ciclu.end(); it++)
        out << *it << " ";

    return 0;
}