Cod sursa(job #2538075)

Utilizator RedXtreme45Catalin RedXtreme45 Data 4 februarie 2020 12:51:43
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#define Nmax 100001
#define Mmax 500001
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m,grad[Nmax],OK,ap[Mmax],nr;
vector <pair<int,int> > G[Nmax];
vector <int> sol;
void euler(int start)
{
    if (!G[start].empty()){
       int x=G[start].back().first;
       int y=G[start].back().second;
       G[start].pop_back();
       if (ap[y]==0)
       {
           ap[y]=1;
           euler(x);
       }
    }
    sol.push_back(start);
}
int main()
{
    int a,b,i,j;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b;
        G[a].push_back({b,i});
        G[b].push_back({a,i});
        grad[a]++;
        grad[b]++;
    }
    for (i=1;i<=n;i++){
        if (grad[i]%2==1)
        {
            OK=-1;
            break;
        }
    }
    if (OK==-1){
        fout<<-1;
    }
    else{
        euler (1);
            sol.pop_back();
            for (vector <int> :: iterator it=sol.end();it!=sol.begin();--it){
                fout<<*it<<" ";
            }
        }
    return 0;
}