Cod sursa(job #1443579)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 28 mai 2015 10:56:13
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

const int N = 251000;

int n, m, x[2 * N], y[2 * N], verm[2 * N], ver[2 * N], poz[2 * N], rez[2 * N], nr;
vector<int> v[2 * N];

void eul(int nod) {
    ver[nod] = 1;

    while(poz[nod] < v[nod].size()) {
        int mu = v[nod][poz[nod]];

        if(verm[mu]) {
            ++poz[nod];
            continue;
        }

        verm[mu] = 1;
        ++poz[nod];

        eul(x[mu] + y[mu] - nod);
    }

    rez[++nr] = nod;
}

int main() {
    int i;
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    cin >> n >> m;
    for(i = 1; i <= m; ++i) {
        scanf("%d%d", &x[i], &y[i]);

        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }

    for(i = 1; i <= n; ++i) if(v[i].size() & 1) {
        cout << "-1";
        return 0;
    }

    eul(1);

    for(i = 1; i <= nr; ++i)
        cout << rez[i] << " ";

    return 0;
}