Cod sursa(job #2588110)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 24 martie 2020 14:17:34
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define N 500001
using namespace std;

bitset <N> seen;
vector <int> S;
vector <pair <int, int>> G[N];
void go (int i) {
    while (!G[i].empty()) {
        auto save=G[i].back();
        G[i].pop_back();

        if (!seen[save.first])
            seen[save.first]=1,
            go(save.second);
    }
    S.push_back(i);
}

int main (void) {
    ifstream fin ("ciclueuler.in");
    ofstream fout ("ciclueuler.out");
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n, m, k, i, j;
    fin >> n >> m;
    for (k=0; k<m; k++) {
        fin >> i >> j;
        G[i].push_back(make_pair(k, j));
        G[j].push_back(make_pair(k, i));
    }
    fin.close();

    bool ok=1;
    for (i=1; i<=n && ok; i++)
        if (G[i].size()&1)
            ok=0;

    if (ok) {
        go(1);
        for (auto it: S)
            fout << it << ' ';
    }
    else
        fout << -1;

    fout << endl;
    fout.close();
    return 0;
}