Cod sursa(job #2541024)

Utilizator danutbodbodnariuc danut danutbod Data 7 februarie 2020 22:53:24
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#define N 100003
#define M  500003
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
struct nod{
    int x;     //nod
    int index; //pozitie muchie in lista de muchii mu[]
    nod*urm;
 };
 nod *L[N];
 nod*p;
 struct muchie{int x,y,selectata;};
 muchie mu[M];
 int sol[M],gr[N];
 int i,j,m,n,k,x,y;
void adauga(int i,int j,int ind){//pune in coada lui i(L[i]) nodul j
  nod*p;                 //ind este pozitia muchiei in lista mu[]
  p=new nod;
  p->x=j;        //pune in coada lui i nodul j
  p->index=ind;
  p->urm=L[i];
  L[i]=p;
 }
void Euler(int j){
   nod *p;
   p=L[j];
   while(p){
    if(mu[p->index].selectata==0)//muchia nu a fost folosita
     {
       mu[p->index].selectata=1;
       Euler(p->x);
     }
     p=p->urm;
   }
 sol[++k]=j;
}


int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
        fi>>x>>y;
        gr[x]++;
        gr[y]++;
        mu[i].x=x;mu[i].y=y;
        adauga(x,y,i);
        if(x!=y)adauga(y,x,i); //sa nu greseasca la bucle 2 2
    }
    bool ok=true;
    for(i=1;i<=n;i++)
        if(gr[i]%2==1)ok=false;
    if(ok==false)fo<<-1;
    else
        {
         Euler(1);
         for(i=1;i<=k-1;i++)fo<<sol[i]<<" ";
        }
return 0;
}