Lavirint

Tezej je došao do Lavirinta u kome se nalazi Minotaur kako bi spasao Arijadnu. Lavirint do koga je došao je specifičan. Ima samo jedan ulaz i jedan izlaz. Dodatno, kako bi uspeo da spase Arijadnu, nije dovoljno da izađe iz lavirinta, neophodno je i da prođe kroz svaki hodnik, ali ne sme da prođe više puta istim putem. Na kraju svakog hodnika stoji pravac kako bi znao kojim hodnicima je dozvoljeno da se dalje kreće. Tezej može da spase Arijadnu čak i ako ne uđe u lavirint. Uslov za to je da je lavirint konstruisan tako da ne postoji put iz njega. Ukoliko put pod opisanim uslovima postoji, Tezej mora da pronađe ulaz u lavirint, uđe u njega, ubije Minotaura i izađe napolje.

Opis ulaza

Sa standardnog ulaza se unose vrednosti \(n\) i \(m\) koje predstavljaju broj raskrsnica u lavirintu i broj hodnika u istom. Nakon toga se sa 2 vrednosti opisuju svi hodnici u lavirintu.

Opis izlaza

Na standardni izlaz ispisati Nemoguce ukoliko Tezej ne treba da ulazi u lavirint kako bi spasao Arijadnu ili put kojim mora proći kako bi uspešno izašao iz lavirinta.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Rešavanje opisanog problema se svodi na proveru da li Ojlerov put postoji u usmerenom grafu, i ako postoji na njegovo pronalaženje.

Prvo je potrebno ustanoviti da li put postoji, odnosno da li postoje početni i krajnji čvor u putu. Početni čvor je čvor grafa za koji važi da je broj izlaznih grana za jedan veći od broja ulaznih grana, dok je kod krajnjeg čvora broj ulaznih grana za jedan veći od broja izlaznih grana. Za sve ostale čvorove mora da važi da je broj ulaznih grana jednak broju izlaznih grana.

Nakon što smo sigurni da put u grafu postoji, možemo primenti Hierholzerov algoritam kako bismo ga i pronašli. U svakom koraku algoritma, iz trenutnog čvora u kome se nalazimo idemo u prvog neposećenog suseda, i “brišemo” granu ka tom susedu (u implementaciji izbacujemo suseda iz liste povezanosti odgovarajućeg čvora). Kada iz nekog čvora nemamo gde da idemo (nema više grana iz njega jer su sve “obrisane” ili ih nije ni bilo), dodajemo treunutni čvor na početak vektora koji predstavlja Ojlerov put i vraćamo se unazad do prvog čvora iz koga ima izlaznih grana. Algoritam rekurzivno nastavljamo dok ne “obrišemo” sve grane iz grafa.

Kako Hierholzerov algoritam predstavlja jednostavnu modifikaciju DFS obilaska grafa, njegova složenost 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;
   vector<int> ulazni_stepeni;
   vector<int> izlazni_stepeni;
   int pocetni_cvor;
   int krajnji_cvor;

public:
   Graph(int broj_cvorova) {
      this->broj_cvorova = broj_cvorova;
      lista_suseda.resize(broj_cvorova);
      ulazni_stepeni.resize(broj_cvorova, 0);
      izlazni_stepeni.resize(broj_cvorova, 0);
      pocetni_cvor = -1;
      krajnji_cvor = -1;
   }

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

      izlazni_stepeni[u]++;
      ulazni_stepeni[v]++;
   }

   bool ojlerov_put_postoji() {
      for (int i = 0; i < broj_cvorova; i++) {
         if (izlazni_stepeni[i] == ulazni_stepeni[i] + 1) {
            if (pocetni_cvor != -1) {
               return false;
            }

            pocetni_cvor = i;
         }
         else if (ulazni_stepeni[i] == izlazni_stepeni[i] + 1) {
            if (krajnji_cvor != -1) {
               return false;
            }

            krajnji_cvor = i;
         }
         else if (ulazni_stepeni[i] != izlazni_stepeni[i]) {
            return false;
         }
      }

      return true;
   }

   void hierholzer(int cvor, vector<int> &ojlerov_put) {
      while (izlazni_stepeni[cvor] > 0) {
         int sused = lista_suseda[cvor][0];
         lista_suseda[cvor].erase(lista_suseda[cvor].begin());
         izlazni_stepeni[cvor]--;
         hierholzer(sused, ojlerov_put);
      }

      ojlerov_put.insert(ojlerov_put.begin(), cvor);
   }

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

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

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

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

   int pronadji_pocetni_ulaz() {
      return pocetni_cvor;
   }
};

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_put(G->pronadji_pocetni_ulaz());

   delete G;
   return 0;
}