Cod sursa(job #2846685)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 9 februarie 2022 15:21:06
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f ( "ciclueuler.in" );
ofstream g ( "ciclueuler.out" );
const int NMAX = 100001;
vector<int>G[NMAX];
vector<int>ciclu;
pair<int, int>muchii[NMAX * 5];
bool used[5 * NMAX];
void Euler ( int x )
{
    while ( G[x].size() > 0 )
    {
        int node = G[x].back();
        G[x].pop_back();

        if ( !used[node] )
        {
            used[node] = 1;
            int n1 = muchii[node].first;
            int n2 = muchii[node].second;

            if ( n1 == x )
                Euler ( n2 );
            else Euler ( n1 );
        }
    }

    ciclu.pb ( x );
}
int main()
{
    int N, M;
    f >> N >> M;

    for ( int i = 1; i <= M; i++ )
    {
        int x, y;
        f >> x >> y;
        G[x].pb ( i );
        G[y].pb ( i );
        muchii[i] = mp ( x, y );
    }

    bool ok = 1;

    for ( int i = 1; i <= N; i++ )
        if ( G[i].size() % 2 != 0 )
            ok = 0;

    if ( ok )
    {
        Euler ( 1 );
        ciclu.pop_back();

        for ( auto i : ciclu )
            g << i << ' ';
    }
    else g << -1;

    return 0;
}