Cod sursa(job #2588107)

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

bitset <N> seen;
stack <int> S;
vector <pair <int, int>> G[N];
void go (int i) {
    for (auto it: G[i])
        if (!seen[it.first])
            seen[it.first]=1,
            go(it.second);
    S.push(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);
        while (S.size()>1) {
            fout << S.top() <<  ' ';
            S.pop();
        }
    }
    else
        fout << -1;

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