Cod sursa(job #3003305)

Utilizator 100pCiornei Stefan 100p Data 15 martie 2023 17:31:31
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

#define MAX 100000
#define FILES freopen("ciclueuler.in","r",stdin);\
              freopen("ciclueuler.out","w",stdout);
#define mod 666013

using namespace std;

int n, m, a, b;
vector<pair<int,int>> graph[MAX + 5];
bool check[MAX * 5 + 1];
vector<int> ans;

stack<int> stack_dfs;

void dfs(int x)
{
    while(!stack_dfs.empty())
    {
        int x = stack_dfs.top();
        bool ok = 0;
        while(graph[x].size() > 0)
        {
            int edge = graph[x].back().second, node = graph[x].back().first;
            if(check[edge])
            {
                graph[x].pop_back();
                continue;
            }
            ok = 1;
            stack_dfs.push(node);
            check[edge] = 1;
            graph[x].pop_back();
            break;
        }
        if(!ok)
        {
            ans.push_back(stack_dfs.top());
            stack_dfs.pop();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    FILES
    std::cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        std::cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    for(int i = 1; i <= n; ++i)
    {
        if(graph[i].size() % 2)
        {
            std::cout << -1;
            exit(0);
        }
    }
    stack_dfs.push(1);
    dfs(1);
    reverse(ans.begin(), ans.end());
    ans.pop_back();
    for(auto i : ans)
        std::cout << i << ' ';
}