Broj puteva

U mreži, računari su povezani kablovima kroz koje signal može da putuje samo u jednom smeru. Računari su povezani tako da signal poslat sa nekog računara ne može da se vrati do istog računara. Za datu mrežu računara, početni i krajnji računar, odrediti broj puteva od početnog do krajnjeg računara.

Opis ulaza

Sa standardnog ulaza se unosi broj računara \(n\) i broj kablova \(m\). Za svako \(j=1,\ldots,m\) u zasebnoj liniji unosi se početak \(u_j\) i kraj \(v_j\) usmerenog kabla. Nakon toga, unose se dva računara \(s\) i \(t\).

Napomena: Pretpostaviti da je \(t\) dostižan iz \(s\), tj. da postoji put od \(s\) do \(t\).

Opis izlaza

Na standardni izlaz ispisati broj mogućih puteva puteva od \(s\) do \(t\).

Primer

Ulaz

5 5
0 1
1 3
1 4
2 1
3 4
0
4

Izlaz

2

Rešenje

Opis glavnog rešenja

Problem možemo svesti na pronalazak broja prostih puteva od čvora \(s\) do čvora \(t\) u usmerenom acikličnom grafu \(G = (V, E)\). Čvorovi grafa će predstavljati računare, dok će grane predstavljati usmerene kablove između računara.

Kako je graf usmeren i acikličan topološkim sortiranjem dobijamo poredak čvorova \(v_1, v_2, \ldots, v_n\). Kako postoji put iz \(s\) do \(t\), onda je \(s\) sigurno pre \(t\) u topološkom poredku. Tada su \(s = v_i, v_{i+1}, \ldots, v_{j-1}, v_j = t\) čvorovi kroz koje može prolaziti neki od traženih puteva, tj. sigurno znamo da ostale čvorove ne treba razmatrati (\(v_1, \ldots, v_{i - 1}\) nisu dostižni iz \(s\), a \(t\) nije dostižan iz \(v_{j + 1}, \ldots, v_n\)). Sada možemo definisati rekurzivnu funkciju \(f(u)\) koja će računati broj prostih puteva iz \(u\) do \(t\): \[\begin{align*} f(u) &= 1, &\qquad u = v_j = t \\ f(u) &= 0, &\qquad u \in \{ v_{j + 1}, \ldots, v_n \} \\ f(u) &= \sum_{v \in \{ v_i, \ldots, v_j \} \\ (u, v) \in E} f(v) &\qquad u \in \{ v_i, \ldots, v_{j - 1} \} \\ \end{align*}\]

Kako je funkcija \(f\) definisana rekurzivno, i pri tome je moguće višestruko pozivanje funkcije \(f\) nad istim čvorom \(u\), složenost izračunavanja funkcije \(f\) možemo poboljšati tehnikom memoizacije, i tada će ona biti \(O(|V| + |E|)\). Kako je topološko sortiranje složenosti \(O(|V| + |E|)\), ukupna složenost algoritma je \(O(|V| + |E|)\).

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <limits>

using namespace std;

class Graph {

private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;
   vector<bool> posecen;
   vector<int> topoloski_poredak;
   vector<pair<int, int>> dodate_grane;
   // Stek koji ce nam je potreban za algoritam topoloskog sortiranja zasnovan na DFS pretrazi grafa
   stack<int> stek;

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

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

   void DFS_topolosko_sortiranje(int u) {
      posecen[u] = true;

      for (int v : lista_suseda[u]) {
         if (!posecen[v]) {
            DFS_topolosko_sortiranje(v);
         }
      }

      // TEK NAKON STO SMO OBISLI SVE NJEGOVE SUSEDE dodajemo element na stek, kako se on nalazi vise na steku bice i
      // ranije uklonjen sa steka pa ce se naci ranije u topoloskom poretku a svi cvorovi koji "zavise" od njega ce se
      // ukloniti kasnije i samim tim ce se naci kasnije u topoloskom poretku
      stek.push(u);
   }

   void topolosko_sortiranje() {
      for (int i = 0; i < broj_cvorova; i++) {
         if (!posecen[i]) {
            DFS_topolosko_sortiranje(i);
         }
      }

      int cvor;

      while (!stek.empty()) {
         cvor = stek.top();
         stek.pop();

         topoloski_poredak.push_back(cvor);
      }
   }

   int num_paths_aid(const int u, const int t, const vector<int> &pi, vector<int> &memo) {
       if (memo[u] != -1) {
           return memo[u];
       }

       if (pi[u] == pi[t]) {
           return memo[u] = 1;
       }

       if (pi[u] > pi[t]) {
           return memo[u] = 0;
       }

       memo[u] = 0;
       for (int v : lista_suseda[u]) {
           if (pi[v] <= pi[t]) {
               memo[u] += num_paths_aid(v, t, pi, memo);
           }
       }
       return memo[u];
   }

   int num_paths(int s, int t) {
       topolosko_sortiranje();

       vector<int> pi(broj_cvorova);
       for (int i = 0; i < topoloski_poredak.size(); i++) {
           pi[topoloski_poredak[i]] = i;
       }

       vector<int> memo(broj_cvorova, -1);
       return num_paths_aid(s, t, pi, memo);
   }
};

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

   int s, t;

   cin >> s >> t;

   cout << G->num_paths(s, t) << endl;

   return 0;
}