Cod sursa(job #2909925)

Utilizator EusebiudistrugatorulLionel Messi Eusebiudistrugatorul Data 16 iunie 2022 21:33:12
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int const N = 2e5 + 5, M = 5e5 + 5;
vector<pair<int, int>> graph[N];
vector<int> cycle;
bitset<M> seen;
stack<int> nodes;
 
void find_eulerian_cycle() {
    nodes.push(1);
    while (!nodes.empty()) {
        int node = nodes.top();
        if (graph[node].size()) {
            int dest = graph[node].back().first, num = graph[node].back().second;
            graph[node].pop_back();
            if (!seen[num]) {
                seen[num] = true;
                nodes.push(dest);
            }
        } else {
            nodes.pop();
            cycle.push_back(node);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int source, dest;
        fin >> source >> dest;
        graph[source].push_back({dest, i});
        graph[dest].push_back({source, i});
    }
    for (int i = 1; i <= n; ++i) {
        if (graph[i].size() % 2) {
            fout << -1;
            return 0;
        }
    }
    find_eulerian_cycle();
    cycle.pop_back();
    for (int nr : cycle) {
        fout << nr << ' ';
    }
    return 0;
}