Opis glavnog rešenja

Rešavanje ovog problema svodi se na proveru da li Ojlerov ciklus postoji u neusmerenom grafu, i ako postoji – na njegovo pronalaženje.

Prvo je potrebno ustanoviti da li ciklus postoji. Za neusmeren graf važi da Ojlerov ciklus postoji ako i samo ako su stepeni svih čvorova parni. Intuitivno, svaki put kada uđemo u čvor nekom granom, moramo iz njega i izaći nekom drugom granom, pa ukupan broj grana incidentnih tom čvoru mora biti paran. U zadatku je dodatno pretpostavljeno da je graf povezan, čime su zadovoljeni svi uslovi za postojanje Ojlerovog ciklusa.

Nakon što smo sigurni da ciklus postoji, primenjujemo Hierholzerov algoritam kako bismo ga konstruisali. Algoritam započinje iz proizvoljnog čvora (u implementaciji iz čvora 0, pod pretpostavkom da ima bar jednu granu). U svakom koraku iz trenutnog čvora prelazimo u nekog njegovog suseda preko neiskorišćene grane i tu granu „brišemo“. Pošto je graf neusmeren, to znači da uklanjamo tu granu iz liste suseda oba čvora.

Kada iz trenutnog čvora više ne postoji nijedna neiskorišćena grana, taj čvor dodajemo u vektor koji predstavlja Ojlerov ciklus i vraćamo se unazad. Na ovaj način se prvo formiraju manji ciklusi, koji se zatim spajaju u jedan veći ciklus. Dodavanje čvorova se vrši tek kada se „zaglavimo“, tj. nema neiskorišćenih grana iz tekućeg čvora, pa se ciklus praktično konstruiše unazad.

Algoritam se rekurzivno nastavlja sve dok se ne obrišu sve grane iz grafa, čime se garantuje da je svaka grana posećena tačno jednom. Dobijeni niz čvorova predstavlja traženi Ojlerov ciklus, odnosno rutu maratona koja prolazi svakom ulicom tačno jednom i vraća se u početni čvor.

Pošto je svaka grana obrađena tačno jednom, složenost Hierholzerovog algoritma je \(O(V + E)\).

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Graph {

private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;

public:
   Graph(int broj_cvorova) {
      this->broj_cvorova = broj_cvorova;
      lista_suseda.resize(broj_cvorova);
   }

   void dodaj_granu(int u, int v) {
      lista_suseda[u].push_back(v);
      lista_suseda[v].push_back(u);
   }

   bool ojlerov_ciklus_postoji() {
      for (int i = 0; i < broj_cvorova; i++) {
         if (lista_suseda[i].size() % 2) {
            return false;
         }
      }

      return true;
   }

   void hierholzer(int cvor, vector<int> &ojlerov_ciklus) {
      while (!lista_suseda[cvor].empty()) {
         int sused = lista_suseda[cvor].back();
         lista_suseda[cvor].pop_back();

         auto za_brisanje = find(lista_suseda[sused].begin(), lista_suseda[sused].end(), cvor);
         lista_suseda[sused].erase(za_brisanje);
         hierholzer(sused, ojlerov_ciklus);
      }

      ojlerov_ciklus.push_back(cvor);
   }

   void pronadji_ciklus(int u) {
      if (!ojlerov_ciklus_postoji()) {
         cout << "Nemoguce!\n";
         return ;
      }

      vector<int> ojlerov_ciklus;
      hierholzer(u, ojlerov_ciklus);

      for (int x : ojlerov_ciklus) {
         std::cout << x << " ";
      }

      std::cout << "\n";
   }

};

int main ()
{
   int n, m;

   cin >> n >> m;

   Graph *G = new Graph(n);

   int u, v;
   for (int i = 0; i < m; i++) {
      cin >> u >> v;
      G->dodaj_granu(u, v);
   }

   G->pronadji_ciklus(0);

   delete G;
   return 0;
}