Cod sursa(job #2735101)

Utilizator AlexBosneag26Bosneag Alexandru AlexBosneag26 Data 1 aprilie 2021 20:12:26
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 100001, M = 500001;

vector <int> a[N], sol;

int grad[N], c = 1;

struct muchie{
    int x, y;
    bool anulat;
}e[M];

void adauga(int x, int y)
{
    a[x].push_back(c);
    a[y].push_back(c);
    e[c] = {x, y, false};
    c++;
}

void euler(int x)
{
    for(int j = a[x].size()-1; j >= 0; j--)
    {
        int i = a[x][j];
        a[x].pop_back();
        if(e[i].anulat)
            continue;
        int y = e[i].x + e[i].y - x;
        e[i].anulat = true;
        euler(y);
    }
    out << x << " ";
}


int main()
{
    int n, m, x, y;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y;
        adauga(x, y);
        grad[x]++;
        grad[y]++;
    }
    for(int i = 1; i <= n; i++)
    {
        if(grad[i] % 2 == 1)
            {out << -1; return 0;}

    }

    euler(1);
    return 0;
}