Cod sursa(job #2152217)

Utilizator osiaccrCristian Osiac osiaccr Data 5 martie 2018 12:51:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#define DEFN 100010
#define DEFM 500010

using namespace std;

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

vector < pair < int, int > > L[DEFN];

int n, m;

bool M[DEFM];

vector < int > Sol;

void dfs (int v); ///Dfs implementat iterativ cu o stiva;

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        L[x].push_back (make_pair (y, i));
        L[y].push_back (make_pair (x, i));
    }

    for (int i = 1; i <= n; ++ i) {
        if (L[i].size () % 2 == 1) {
            fout << -1;
            return 0;
        }
    }

    dfs (1);

    for (int i = 0; i < Sol.size (); ++ i) {
        fout << Sol[i] << " ";
    }
}

void dfs (int v) {
    vector < int > St;
    St.push_back (v);
    while (!St.empty ()) {
        int u = St.back ();
        if (!L[u].empty ()) {
            pair < int, int > w = L[u].back ();
            L[u].pop_back ();
            if (!M[w.second]) {
                M[w.second] = 1;
                St.push_back (w.first);
            }
        }
        else {
            St.pop_back ();
            Sol.push_back (u);
        }
    }
}