Cod sursa(job #2225096)

Utilizator HumikoPostu Alexandru Humiko Data 25 iulie 2018 21:40:53
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define lim 100001

using namespace std;

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

int n, m;
int f[lim*5];

vector <pair<int, int>> graph[lim];
deque <int> solution;

void checkForEulerianCycle( int node )
{
    int current_Node, current_Edge;

    while ( graph[node].size() )
    {
        current_Node = graph[node].back().first;
        current_Edge = graph[node].back().second;
        graph[node].pop_back();

        if ( f[current_Edge] == 0 )
        {
            f[current_Edge] = 1;
            checkForEulerianCycle(current_Node);
        }
    }

    solution.push_back(node);

    while ( solution.size() )
    {
        fout<<solution.front()<<" ";
        solution.pop_front();
    }
}

int main()
{
    fin>>n>>m;
    for ( int i = 1; i <= m; ++i )
    {
        int first_Node, second_Node;
        fin>>first_Node>>second_Node;

        graph[first_Node].push_back({second_Node, i});
        graph[second_Node].push_back({first_Node, i});
    }

    for ( int i = 1; i <= n; ++i )
    {
        if ( graph[i].size()%2 )
        {
            fout<<'-1'<<'\n';
            return 0;
        }
    }

    checkForEulerianCycle(1);
}