Cod sursa(job #2385331)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 21 martie 2019 20:08:04
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#define DMAX 100005
#define NMAX 500005

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
struct varf{int v; int ind;};
vector<varf> LA[DMAX];
int n;
bool uz1[DMAX];
bool uzm[NMAX];
int g[DMAX];
void citire();
void euler();
bool verif();
void DFS1(int x);
void DFS(int x);
int main()
{
    citire();
    if(verif())
       {euler();fout<<'\n';}
       else
       fout<<'-1'<<'\n';
    return 0;
}
void citire()
{int a,b,M,i;
 varf aux;
    fin>>n;
    fin>>M;
    for(i=1;i<=M;i++)
         {
          fin>>a>>b;
          aux.v=b;
          aux.ind=i;
          LA[a].push_back(aux);
          if(a!=b)
            {aux.v=a;
             LA[b].push_back(aux);
            }
          g[a]++;
          g[b]++;
         }
}
bool verif()
{int i;
   DFS(1);
   for(i=1;i<=n;i++)
       {if(uz1[i]==0)
           return 0;
        if(g[i]%2)
           return 0;
       }
   return 1;
}
void DFS(int x)
{int i;
 uz1[x]=1;
    for(i=0;i<LA[x].size();i++)
        if(!uz1[LA[x][i].v])
           DFS(LA[x][i].v);
}
void euler()
{
    g[1]--;
    DFS1(1);
}
void DFS1(int x)
{int i,j;
    for(i=0;i<LA[x].size();i++)
        if(uzm[LA[x][i].ind]==0&&g[LA[x][i].v]>0)
           {uzm[LA[x][i].ind]=1;
            g[LA[x][i].v]--;
            DFS1(LA[x][i].v);
           }
    fout<<x<<' ';
}