Cod sursa(job #2570463)

Utilizator Antonio020712Potra Antonio Antonio020712 Data 4 martie 2020 16:59:32
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 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];
int grad[NMAX];
vector<int> drum;
vector<pair<int, int> > g[NMAX];

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

    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y;
        grad[x]++;
        grad[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() {
    int i;

    citire();
    dfs(1);

    for (i = 1; i <= n; i++)
        if (grad[i] % 2 == 1) {
            fout << -1 << ' ';
            return 0;
        }
    drum.pop_back();
    while(!drum.empty()) {
        fout << drum.back() << ' ';
        drum.pop_back();
    }

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

    return 0;
}