Cod sursa(job #2369295)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 5 martie 2019 22:15:52
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m;
vector<pair<int, int>>G[100001];
vector<int>Cycle;
bool viz[500001];

void euler(int nod)
{
    while(!G[nod].empty())
    {
        while(!G[nod].empty() && viz[G[nod].back().second]) G[nod].pop_back();
        if(!G[nod].empty())
        {
            viz[G[nod].back().second]=1;
            int x=G[nod].back().first;
            G[nod].pop_back();
            euler(x);
        }
    }
    Cycle.push_back(nod);
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        fin>>x>>y;
        G[x].push_back(make_pair(y, i));
        G[y].push_back(make_pair(x, i));
    }
    for(int i=1; i<=n; ++i)
    {
        if(G[i].size()%2==1)
        {
            fout<<"-1\n";
            return 0;
        }
    }

    euler(1);

    for(int i=1; i<=m; ++i)
    {
        if(!viz[i])
        {
            fout<<"-1\n";
            return 0;
        }
    }
    Cycle.pop_back();
    for(auto it:Cycle) fout<<it<<" ";
    fout<<"\n";
    return 0;
}