Cod sursa(job #2570440)

Utilizator Antonio020712Potra Antonio Antonio020712 Data 4 martie 2020 16:48:54
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#define NMAX 100005
#define MMAX 500005

using namespace std;

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

int n, m;
bool vizitat[MMAX];
vector<pair<int, int> > g[NMAX];
vector<int> drum;

void citire() {
    int i, x, y;
    pair<int, int> muchie;

    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y;
        muchie.second = i;
        muchie.first = y;
        g[x].push_back(muchie);
        muchie.first = x;
        g[y].push_back(muchie);
    }
}

void dfs(int nod) {
    pair<int, int> e;

    if (g[nod].empty()) {
        drum.push_back(nod);
        return;
    }

    while(!g[nod].empty()) {
        e = g[nod].back();
        g[nod].pop_back();
        if(!vizitat[e.second]) {
            vizitat[e.second] = 1;
            m--;
            dfs(e.first);
        }
    }

    drum.push_back(nod);
}

int main() {
    citire();
    dfs(1);

    if(m > 0)
        fout << -1;
    else {
        drum.pop_back();
        while(!drum.empty()) {
            fout << drum.back() << ' ';
            drum.pop_back();
        }
    }

    fin.close();
    fout.close();

    return 0;
}