Opis glavnog rešenja

Kako su sve grane neusmerenog grafa jednake težine, problem nalaženja najkraćeg puta po broju grana rešava se algoritmom pretrage u širinu. Pretragu pokrećemo iz početnog čvora \(s\). Poznato je da algoritam pretrage u širinu čvorove obilazi po nerastućem rastojanju od početnog čvora, pa prvi put kada stignemo do nekog čvora do njega smo stigli najkraćim mogućim putem.

Pored informacije da li je čvor posećen, za svaki čvor pamtimo i njegovog prethodnika na putu kojim je prvi put dostignut. Kada tokom pretrage iz čvora \(u\) prvi put dođemo do suseda \(v\), postavljamo da je roditelj čvora \(v\) upravo čvor \(u\). Nakon završene pretrage, ako čvor \(t\) nije posećen, put ne postoji. U suprotnom, najkraći put rekonstruišemo tako što od čvora \(t\) pratimo roditelje unazad sve do čvora \(s\), a zatim tako dobijen niz obrnemo.

Vremenska složenost algoritma je \(O(n + m)\), jer se svaki čvor ubacuje u red najviše jednom, a svaka grana se razmatra najviše dva puta.

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

using namespace std;

class Graph {
private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;
   vector<bool> posecen;
   vector<int> roditelj;

public:
   Graph(int broj_cvorova) {
      this->broj_cvorova = broj_cvorova;
      lista_suseda.resize(broj_cvorova);
      posecen.resize(broj_cvorova, false);
      roditelj.resize(broj_cvorova, -1);
   }

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

   vector<int> najkraci_put(int pocetni_cvor, int krajnji_cvor) {
      queue<int> cvorovi;

      cvorovi.push(pocetni_cvor);
      posecen[pocetni_cvor] = true;

      while (!cvorovi.empty()) {
         int cvor = cvorovi.front();
         cvorovi.pop();

         if (cvor == krajnji_cvor) {
            break;
         }

         for (int sused : lista_suseda[cvor]) {
            if (!posecen[sused]) {
               posecen[sused] = true;
               roditelj[sused] = cvor;
               cvorovi.push(sused);
            }
         }
      }

      vector<int> put;

      if (!posecen[krajnji_cvor]) {
         return put;
      }

      int cvor = krajnji_cvor;
      while (cvor != -1) {
         put.push_back(cvor);
         cvor = roditelj[cvor];
      }

      reverse(put.begin(), put.end());
      return put;
   }
};

int main ()
{
   ios_base::sync_with_stdio(false);

   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);
   }

   int s, t;
   cin >> s >> t;

   vector<int> put = G->najkraci_put(s, t);

   if (put.empty()) {
      cout << -1 << "\n";
   } else {
      cout << put.size() << "\n";
      for (int cvor : put) {
         cout << cvor << " ";
      }
      cout << "\n";
   }

   delete G;
   return 0;
}