Cod sursa(job #3334864)

Utilizator gabi_vag742Vasile Alexandru Gabriel gabi_vag742 Data 20 ianuarie 2026 12:12:59
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, a, b;
vector<vector<pair<int,int>>> g;
vector<int> sol, grad;
vector<bool> viz;

void dfs(int k)
{
    viz[k] = true;

    for(auto i : g[k])
        if(viz[i.first] == false)
            dfs(i.first);
}

void euler(int k)
{
    sol.push_back(k);

    while(g[k].size() > 0)
    {
        int nod = g[k].back().first;
        int muchie = g[k].back().second;

        g.pop_back();

        if(viz[muchie] == false)
        {
            viz[muchie] == true;
            euler(nod);
        }
    }
}

int main ()
{
    fin >> n >> m;
    g = vector<vector<pair<int,int>>> (n+1);
    grad = vector<int> (n+1);
    viz = vector<bool> (n+1);

    for(int i = 1; i <= m; i++)
    {
        fin >> a >> b;

        grad[a]++;
        grad[b]++;
        g[a].push_back({b,i});
        g[b].push_back({b,i});
    }

    int ok = 1;

    dfs(1);

    for(int i = 1; i <= n; i++)
        if(viz[i] == false || grad[i] % 2 == 1 )
        {
            ok = 0;
            fout << -1;
            break;
        }

    if(ok)
    {
        viz = vector<bool> (n+1,0);
        euler(1);
    }

    for(auto i : sol)
        fout << i << ' ';

    return 0;
}