Cod sursa(job #3209079)

Utilizator Allie28Radu Alesia Allie28 Data 1 martie 2024 20:30:20
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <queue>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int LMAX = 100005;
const int NMAX = 500005;
vector<pair<int, int>> L[LMAX];
vector<int> sol;
int grad[LMAX];
bool viz[NMAX];

void euler(int node) {
    while (L[node].size()) {
        int vec = L[node].back().first;
        int edge = L[node].back().second;
        L[node].pop_back();
        if (!viz[edge]) {
            viz[edge] = 1;
            euler(vec);
        }
    }
    sol.push_back(node);
}

int main() {
    int n, m, x, y, i, j;
    fin>>n>>m;
    for (i = 0; i < m; i++) {
        fin>>x>>y;
        x--;
        y--;
        L[x].push_back({y, i});
        L[y].push_back({x, i});
        grad[x]++;
        grad[y]++;
    }
    for (i = 0; i < n; i++) {
        if ((grad[i]&1)) {
            fout<<-1; return 0;
        }
    }
    euler(0);

    for (i = 0; i < sol.size() - 1; i++) {
        fout<<sol[i] + 1<<" ";
    }


    fin.close();
    fout.close();
    return 0;
}