Cod sursa(job #2279235)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 9 noiembrie 2018 10:51:46
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

#define NM 100005
#define MM 500005

using namespace std;

struct edge
{
    int u, v;
    bool viz;
    int other(int u)
    {
        return this->u + this->v - u;
    }
};

int n, m;
edge edges[MM];

vector <edge*> gr[NM];

vector <int> ans;

void euler(int u)
{
    while(!gr[u].empty())
    {
        if(gr[u].back()->viz == 0)
        {
            gr[u].back()->viz = 1;
            int v = gr[u].back()->other(u);
            gr[u].pop_back();
            euler(v);
        }
        else
            gr[u].pop_back();
    }
    ans.push_back(u);
}

int main()
{
    ifstream fin ("ciclueuler.in");
    ofstream fout ("ciclueuler.out");
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> edges[i].u >> edges[i].v;
        edges[i].viz = 0;
        gr[edges[i].u].push_back(&edges[i]);
        gr[edges[i].v].push_back(&edges[i]);
    }
    euler(1);
    if(ans.size() != m + 1 || ans.front() != ans.back())
        fout << "-1\n";
    else
    {
        ans.pop_back();
        for(auto i : ans)
            fout << i << " ";
    }
    return 0;
}