Cod sursa(job #2745987)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 27 aprilie 2021 12:42:33
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
const int dim=501009;
int viz[dim];

void Euler(int nod,vector< pi > V[],vector < int >& ans)
{
    while(V[nod].size())
    {
        int neigh=V[nod].back().first;
        int idx=V[nod].back().second;
        V[nod].pop_back();

        if(!viz[idx])
        {
            viz[idx]=1;
            Euler(neigh,V,ans);
        }
    }
    ans.pb(nod);
}

int main(int argc,char** argv)
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");

    int n,m,x,y;
    f>>n>>m;
    vector < pi > V[n+1];
    vector < int >ans;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        V[x].pb({y,i});
        V[y].pb({x,i});
    }
    for(int i=1;i<=n;i++)
        if(V[i].size()%2)
        {
            g<<-1;
            return 0;
        }

    Euler(1,V,ans);

    reverse(ans.begin(),ans.end());
    ans.pop_back();
    for(int x:ans) g<<x<<' ';

    return 0;
}