Cod sursa(job #3327129)

Utilizator zionlyismAdobroaiei David zionlyism Data 2 decembrie 2025 15:22:51
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

#define NMAX 100002
#define MMAX 500002
using namespace std;

ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");

int n, m;
int nxt, nr;
int grad[NMAX];
bool gradeok = 1;

vector<vector<pair<int, int>>> graf;
bitset<MMAX>muchie; //muchie[i] = 1 daca a fost vizitat si 0 altfel
int unde[NMAX]; //unde[i];  unde am ramas cu verificarea muchiilor nodului i

queue<int> Q;

void citire();
void Euler(int nod);

int main()
{
    int i, aux = 0;
    citire();
    Euler(1);
    for(i = 1; i <= m; i++) aux += muchie[i];
    for(i = 1; i <= n; i++)
        if(grad[i] % 2 == 1 || grad[i] == 0)
           gradeok = 0;
    if(aux == m && gradeok) //am vizitat toate muchiile
    {
       while(!Q.empty())
       {
           fout<<Q.front()<<' '; Q.pop();
       }
    }
    else
    fout<<-1<<'\n';
    return 0;
}

void Euler(int nod)
{
 int i;
 for(i = unde[nod]; i < graf[nod].size(); i++)
    {
     nxt = graf[nod][i].first;
     nr = graf[nod][i].second;
     if(!muchie[nr]) //daca nu am mai fost pe aceasta muchie
     {
        unde[nod] = i + 1;
        muchie[nr] = 1;
        Euler(nxt);
     }
    }
 Q.push(nod);
}

void citire()
{
 int i, x, y;
 fin>>n>>m;
 graf.resize(n + 2);
 for(i = 1; i <= m; i++)
 {
     fin>>x>>y;
     grad[x]++; grad[y]++;
     graf[x].push_back({y, i});
     graf[y].push_back({x, i});
 }
}