Cod sursa(job #2712401)

Utilizator Fatu_SamuelFatu Samuel Fatu_Samuel Data 25 februarie 2021 18:48:04
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <stack>

using namespace std;

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

const int nMax = 1 * 100000 + 10;
const int mMax = 5 * 100000 + 10;

struct Node
{
    int next, edge;
};

int n, m;
vector < Node > l[nMax];
vector < int > r;
bitset < mMax > viz;
stack < int > stk;

void Dfs(int node)
{ 
    stk.push(node);

    while (!stk.empty())
    {
        node = stk.top();
        
        if (!l[node].empty())
        {
            int next = l[node].back().next;
            int edge = l[node].back().edge;

            l[node].pop_back();

            if (!viz[edge])
            {
                viz[edge] = 1;
                stk.push(next);
            }
        }
        else
        {
            stk.pop();
            r.push_back(node);
        }
    }
}

int main()
{
    bool euler = true;

    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b;

        fin >> a >> b;

        l[a].push_back({b, i});
        l[b].push_back({a, i});
    }

    

    for (int i = 1; i <= n && euler; i++)
    {
        if (l[i].size() % 2)
        {
            euler = false;
        }
    }
    
    
    if (euler)
    {
        Dfs(1);
        
        int rSize = r.size() - 1;

        for (int i = 0; i < rSize; i++)
        {
            fout << r[i] << ' ';
        }
    }
    else
    {
        fout << "-1";
    }
    

    fin.close();
    fout.close();
    return 0;
}