Cod sursa(job #2696691)

Utilizator radubigColtos Radu radubig Data 16 ianuarie 2021 13:27:06
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>

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

pair<int, int> a[500005];
vector<int> v[100005];
vector<int> ans;
int n, m;
bool viz[500005];
int gr[100005];

bool verif()
{
    for(int i=1; i<=n; i++)
        if(gr[i]%2==1) return false;
    return true;
}

void euler(int poz)
{
    while(!v[poz].empty())
    {
        int muchie = v[poz].back();
        v[poz].pop_back();
        if(viz[muchie])
            continue;
        viz[muchie]=1;
        int vecin = poz ^ a[muchie].first ^ a[muchie].second;
        euler(vecin);
    }
    ans.push_back(poz);
}

int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>a[i].first>>a[i].second;
        v[a[i].first].push_back(i);
        v[a[i].second].push_back(i);
        gr[a[i].first]++; gr[a[i].second]++;
    }

    if(verif())
    {
        euler(1);
        ans.pop_back();
        for(int i : ans)
            out<<i<<' ';
    }
    else
        out<<-1;
    return 0;
}