U fabrici postoji \(n\) zavisnih zadataka. Zavisnosti su zadate usmerenim vezama: ako postoji veza \(u \rightarrow v\), zadatak \(u\) mora biti završen pre zadatka \(v\). Zadaci koji nemaju nezavršene preduslove u tom trenutku smatraju se spremnim.
Potrebno je utvrditi da li je dati raspored moguć. Ako jeste moguć, odrediti minimalan broj dana \(d\) potrebanih da se završe svi zadaci.
Sa standardnog ulaza se unosi broj zadataka \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) i broj veza \(m\) (\(1 \leq m \leq 4 \cdot 10^5\)). U narednih \(m\) linija, unose se dva broja \(u\) i \(v\) (\(1 \leq u, v \leq n\), \(u \noteq v\)).
Na standardni izlaz ispisati minimalan broj dana \(d\), koji je potreban da se završe svi zadaci. Ukoliko nije moguće odrediti raspored, ispisati -1.
5 4 1 3 2 3 3 4 2 5
3
Prvog dana se završe zadaci 1 i 2. Drugog dana se završe zadaci 3 i 5. I trećeg dana se završi zadatak 4.
3 3 1 2 2 3 3 1
-1
Zadatak 2 je uslovljen zadatkom 1; zadatak 1 je uslovljen zadatkom 3; i zadatak 3 je uslovljen zadatkom 2. Ni jedan zadatak se ne može završiti.
Zadatak rešavamo modifikovanim Kanovim algoritmom za topološko sortiranje. Za svaki zadatak pamtimo broj njegovih nezavršenih preduslova, tj. ulazni stepen u odgovarajućem usmerenom grafu.
Na početku su spremni svi zadaci čiji je ulazni stepen jednak nuli. Njih sme da se izvrši prvog dana, pa ih stavljamo u red. Zatim radimo po danima. U svakom koraku iz reda uzimamo sve zadatke koji su u tom trenutku spremni i izvršavamo ih istog dana. Kada se neki zadatak izvrši, obilazimo sve njegove izlazne grane i smanjujemo ulazni stepen odgovarajućih suseda. Ako nekom susedu ulazni stepen postane nula, on postaje spreman i može da se izvrši narednog dana.
Broj iteracija ovog postupka jednak je minimalnom broju dana potrebnih da se svi zadaci završe, jer svakog dana izvršavamo sve zadatke koji su u tom trenutku dostupni. Ako u nekom trenutku red postane prazan, a još uvek postoje neizvršeni zadaci, tada u grafu postoji ciklus i traženi raspored ne postoji.
Složenost algoritma je \(O(n + m)\), jer se svaki zadatak ubacuje u red najviše jednom, a svaka usmerena veza se obrađuje tačno jednom.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph {
private:
int broj_cvorova;
vector<vector<int>> lista_suseda;
vector<int> ulazni_stepeni;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
lista_suseda.resize(broj_cvorova);
ulazni_stepeni.resize(broj_cvorova, 0);
}
void dodaj_granu(int u, int v) {
lista_suseda[u].push_back(v);
ulazni_stepeni[v]++;
}
int topolosko_sortiranje_broj_dana() {
queue<int> spremni_cvorovi;
for (int u = 0; u < broj_cvorova; u++) {
if (ulazni_stepeni[u] == 0) {
spremni_cvorovi.push(u);
}
}
int broj_dana = 0;
int obradjeno = 0;
while (obradjeno < broj_cvorova) {
if (spremni_cvorovi.empty()) {
return -1;
}
int broj_spremnih = spremni_cvorovi.size();
vector<int> danas;
for (int i = 0; i < broj_spremnih; i++) {
danas.push_back(spremni_cvorovi.front());
spremni_cvorovi.pop();
}
for (int u : danas) {
for (int v : lista_suseda[u]) {
ulazni_stepeni[v]--;
if (ulazni_stepeni[v] == 0) {
spremni_cvorovi.push(v);
}
}
obradjeno++;
}
broj_dana++;
}
return broj_dana;
}
};
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 - 1, v - 1);
}
cout << G->topolosko_sortiranje_broj_dana() << endl;
delete G;
return 0;
}