Cod sursa(job #3343243)

Utilizator Victor5539Tanase Victor Victor5539 Data 26 februarie 2026 18:26:32
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>


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


const int NMAX=1e5,MMAX=5e5;
int n,i,m,node1,node2,nr,deg[NMAX+5];
bool viz[NMAX+5],viz_edge[MMAX+5];
vector <pair<int,int>> adj[NMAX+5];
vector <int> sol;

void dfs(int node)
{
    viz[node]=1;
    nr++;

    for (auto edge: adj[node])
        if (!viz[edge.first])
            dfs(edge.first);
}

void Euler(int node)
{
    while (!adj[node].empty())
    {
        pair <int,int> edge=adj[node].back();
        adj[node].pop_back();

        int node2=edge.first,idx=edge.second;

        if (!viz_edge[idx])
        {
            viz_edge[idx]=1;
            Euler(node2);
        }
    }

    sol.push_back(node);
}


int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr); fout.tie(nullptr);

    fin>>n>>m;

    for (i=1; i<=m; i++)
    {
        fin>>node1>>node2;
        adj[node1].push_back({node2,i});
        adj[node2].push_back({node1,i});
        deg[node1]++;
        deg[node2]++;
    }

    for (i=1; i<=n; i++)
        if (deg[i]%2!=0)
            {
                fout<<-1;
                return 0;
            }

    dfs(1);

    if (nr!=n)
    {
        fout<<-1;
        return 0;
    }

    Euler(1);

    for (auto x: sol)
        fout<<x<<" ";





    return 0;
}