Cod sursa(job #2574157)

Utilizator PatriciaCretoiuCretoiu Patricia PatriciaCretoiu Data 5 martie 2020 20:39:23
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

const int N = 1e5 + 5;
const int M = 5e5 + 5;
vector <pair<int, int>> G[N];
vector <int> ans;
bitset <M> viz;

void euler(int node)
{
    while(G[node].size())
    {
        int neig = G[node].back().first;
        int edge = G[node].back().second;
        G[node].pop_back();
        if(viz[edge] == 0)
        {
            viz[edge] = 1;
            euler(neig);
        }
    }
    ans.push_back(node);
}

int main()
{
    ios::sync_with_stdio(false);
    in.tie(0);

    int n, m;
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        G[x].push_back({y,i});
        G[y].push_back({x,i});
    }

    for(int i = 1; i <= n; i++)
        if(G[i].size() & 1)
        {
            out << -1;
            return 0;
        }

    euler(1);

    for(size_t j = 0; j < ans.size() - 1; j++)
        out << ans[j] << ' ';
}