Cod sursa(job #2375732)

Utilizator ARobertAntohi Robert ARobert Data 8 martie 2019 11:51:04
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define ll long long
#define lf long double

using namespace std;

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

int n,m,a,b,viz[500005],grad[100005],ok;
vector<pair<int,int>>v[100005];
vector<int> rasp;
stack<int> s;

int main()
{
    ios_base::sync_with_stdio(false);
    fin>>n>>m;
    ok=1;
    for (int i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back({i,b});
        v[b].push_back({i,a});
        grad[a]++;
        grad[b]++;
    }
    for (int i=1;i<=n;i++)
        if (grad[i]==0||grad[i]%2==1)
            ok=0;
    if (ok==1)
    {
        s.push(1);
        while (!s.empty())
        {
            int i=s.top();
            if (v[i].size())
            {
                int muchie=v[i].back().first;
                int nod=v[i].back().second;
                v[i].pop_back();
                if (!viz[muchie])
                {
                    viz[muchie]=1;
                    s.push(nod);
                }
            }
            else
            {
                s.pop();
                rasp.push_back(i);
            }
        }
        for (auto nod:rasp)
            fout<<nod<<" ";
    }
    else fout<<-1;
    return 0;
}

//Long long output!!!
//Check constraints!!!