Cod sursa(job #3224846)

Utilizator unomMirel Costel unom Data 16 aprilie 2024 12:49:43
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int n, m;
vector<int> v[100005];
int mult[100005];
int viz[100005];
vector<int> ans;

void dfs(int node)
{
    viz[node] = 1;

    for(auto it: v[node])
    {
        if(viz[it] == 0)
        {
            dfs(it);
        }
    }
}

void del(int x, int y)
{
    for(int i = 0; i<v[x].size(); i++)
    {
        if(v[x][i] == y)
        {
            swap(v[x][i], v[x][v[x].size() - 1]);
            v[x].pop_back();

            break;
        }
    }
}

void euler(int node)
{
    //cout<<node<<'\n';

    int nxt;
    for(int i = 0; i<v[node].size(); i++)
    {
        nxt = v[node][i];
        swap(v[node][i], v[node][v[node].size() - 1]);
        v[node].pop_back();

        del(v[node][i], node);

        euler(nxt);
    }

    ans.push_back(node);
    while(mult[node] > 0)
    {
        ans.push_back(node);
        mult[node]--;
    }
}

int main()
{
    in>>n>>m;

    int x, y;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y;

        if(x == y)
        {
            mult[x]++;
        }
        else
        {
            v[x].push_back(y);
            v[y].push_back(x);
        }
    }

    dfs(1);

    int ok = 1;
    for(int i = 1; i<=n; i++)
    {
        if(v[i].size() % 2 == 1 || viz[i] == 0)
        {
            ok = 0;
        }
    }

    if(ok == 0)
    {
        out<<-1;
        return 0;
    }

    euler(1);

    for(int i = 0; i<ans.size() - 1; i++)
    {
        out<<ans[i]<<" ";
    }

    return 0;
}