Cod sursa(job #2548590)

Utilizator MarcGrecMarc Grec MarcGrec Data 16 februarie 2020 20:21:08
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#define MAX_N 100000
#define MAX_M 500000
 
#include <fstream>
#include <vector>
#include <bitset>
#include <utility>
using namespace std;
 
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
 
int n, m;
pair<int, int> E[MAX_M + 1];
vector<int> R, G[MAX_N + 1];
 
bool Eulerian();
void Df(int nod);
 
int main()
{
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; ++i)
    {
        fin >> x >> y;
        G[x].push_back(i);
        G[y].push_back(i);
        E[i] = { x, y };
    }
 
    if (!Eulerian())
    {
        fout << "-1";
    }
    else
    {
        Df(1);
 
        for (int nod : R)
        {
            fout << nod << ' ';
        }
    }
 
    fin.close();
    fout.close();
    return 0;
}
 
bool Eulerian()
{
    for (int i = 1; i <= n; ++i)
    {
        if (G[i].size() & 1)
        {
            return false;
        }
    }
    return true;
}
 
bitset<MAX_M + 1> F;
void Df(int nod)
{	
    for (int muchie : G[nod])
    {
        if (!F[muchie])
        {
            F[muchie] = true;
 
            if (E[muchie].first == nod)
            {
                Df(E[muchie].second);
            }
            else
            {
                Df(E[muchie].first);
            }
            break;
        }
    }
    
    R.push_back(nod);
}