Cod sursa(job #3148769)

Utilizator danutbodbodnariuc danut danutbod Data 4 septembrie 2023 07:32:02
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <fstream>
#include <bitset>
#include <vector>
#define MAX 100003
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");

int n,m,x,y;
bitset < 5*MAX > viz;      //pentru stergerea muchiilor vizitate
struct muchie {int x,y;} E[5*MAX];//memorarea muchiilor
vector < int > G[MAX],ciclu;

int VerifEulerian(){
     for(int i=1;i<=n;i++)
          if(G[i].size()%2==1)return 0;
     return 1;
}
inline void DF(int nod){     //fara inline la 3 teste crapa stiva?
     for(int i=0;i<G[nod].size();i++)
          if(!viz[G[nod][i]])
            {
                viz[G[nod][i]]=1;
                DF(E[G[nod][i]].x+E[G[nod][i]].y-nod);//(x+y)-x==y
            }
     ciclu.push_back(nod);
}

int main()
{
     fi>>n>>m;
     for(int i=1;i<=m;i++)
     {
          fi>>x>>y;
          G[x].push_back(i); G[y].push_back(i);//memorez indicele muchiei
          E[i].x=x,E[i].y=y;               //memorez muchia cu indicele i
     }
     if(VerifEulerian())
     {
          DF(1);
          for(int i=0;i<ciclu.size();i++)fo<<ciclu[i]<<' ';
          fo<<'\n';
     }
     else fo<<-1<<'\n';
     return 0;
}

//#include <bits/stdc++.h>
//using namespace std;
//vector <long long> a;
//vector <long long> s(100003,0); //trebuie alocat daca vrem sa aiba val 0  !!!!
//vector <long long> ::iterator it;
//int i,n,x;
//int main()
//{
//  cin>>n;
//  for(i=1;i<=n;i++)
//  {
//      cin>>x;a.push_back(x);
//  }
//  //precalculare sume partiale
//  s[0]=0;
//  for(i=0;i<n;i++)
//    s[i+1]=s[i]+a[i+1];
//    for(i=0;i<n;i++)
//        cout<<s[i]<<" ";
//   cin>>m;
//   for(i=1;i<=m;i++)
//   {
//       cin>>x>>y;
//       if(x>y)swap(x,y);
//       sum=s[y]-s[x-1];
//   }
//
//
//    return 0;
//}

//#include<bits/stdc++.h>
//using namespace std;
//ifstream fi("paritar.in");
//ofstream fo("paritar.out");
//vector <int> a,b;
//vector <int> ::iterator it;
//int i,n,x,minip,minii,M=10000000;
//int main()
//{
//    fi>>n;
//    for(i=1;i<=n;i++)
//    {
//        fi>>x;
//        a.push_back(x);
//    }
//    minip=M;
//    minii=M;
//    for(i=1;i<=n;i++)
//    {
//        fi>>x;
//        if(x%2==0 and minip>x)minip=x;
//        if(x%2==1 and minii>x)minii=x;
//    }
//
//  //fo<<minip<<" "<<minii<<endl;
//    bool ok=true;
//    for(it=a.begin();it!=a.end();it++)
//      {
//        if((*it)%2==0)
//          if(minii!=M and minii<(*it))ok=false;
////        if((*it)%2==1)
////          if(minip!=M and minip<(*it))ok=false;
//      }
//    if(ok)fo<<"DA";
//    else fo<<"NU";
//    fi.close();fo.close();
//    return 0;
//}