Cod sursa(job #3334868)

Utilizator gabi_vag742Vasile Alexandru Gabriel gabi_vag742 Data 20 ianuarie 2026 12:29:44
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 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)
{
    while(g[k].size() > 0)
    {
        int nod = g[k].back().first;
        int muchie = g[k].back().second;

        g[k].pop_back();

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

    sol.push_back(k);
}

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({a,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> (m+1,0);
        euler(1);

        sol.pop_back();
        for(auto i: sol)
            fout << i << ' ';
    }

    return 0;
}