Cod sursa(job #2346810)

Utilizator LivcristiTerebes Liviu Livcristi Data 18 februarie 2019 09:37:04
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define NUM 100005
using namespace std;
vector < pair<int, int> > graf[NUM];
int sol[5 * NUM];
int viz[5 *NUM];
int n, m, a, b, num;
void euler()
{
    stack <int> stiva;
    stiva.push(1);
    while(!stiva.empty())
    {
        int nod = stiva.top();

        if(!graf[nod].size())
        {
            stiva.pop();
            sol[++num] = nod;
            continue;
        }

        int nodNou = graf[nod].back().first;
        int muchie = graf[nod].back().second;
        graf[nod].pop_back();

        if(!viz[muchie])
        {
            viz[muchie] = 1;
            stiva.push(nodNou);
        }
    }
}
int main()
{
    ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> a >> b;
        graf[a].push_back({b, i});
        graf[b].push_back({a, i});
    }

    for(int i = 1; i <= n; ++i)
    {
        if(!graf[i].size() || graf[i].size() % 2)
        {
            g << "-1";
            return 0;
        }
    }

    euler();

    for(int i = 1; i < num; ++i)
        g << sol[i] << " ";

    f.close();
    g.close();
}