Choose your language!

---

|

Topološko sortiranje

Topološko sortiranje je algoritamska tehnika koja pronalazi redosled obilaska čvorova u usmerenom acikličnom grafu (DAG) tako da za svaku usmerenu granu u → v čvor u dolazi pre čvora v u redosledu.

Ovaj proces je ključan u problemima gde postoji redosled zavisnosti.

Slika 1: Vizuelni prikaz topološkog sortiranja u DAG grafu sa DFS i Kahn algoritmom. Pogledaj kako se čvorovi redom sortiraju i kako se detektuje ciklus.

Objašnjenje infografike

Slika prikazuje osnovne koncepte topološkog sortiranja u usmerenom acikličnom grafu (DAG). Plavi čvorovi predstavljaju čvorove grafa, strelice označavaju smerove grana. Brojevi pokazuju redosled u kojem algoritam dodaje čvorove u konačni topološki niz.

DFS pristup: Čvorovi se dodaju u stek posle obilaska svih svojih suseda. Ako postoji ciklus, stek neće moći da obuhvati sve čvorove.

Kahn-ov algoritam: Čvor sa indegree = 0 se uklanja i smanjuje indegree susedima. Ako ostanu čvorovi sa indegree > 0, graf sadrži ciklus i topološko sortiranje ne postoji.

Infografika pomaže da odmah vizuelno shvatite kako oba algoritma funkcionišu i kada graf ne može biti sortirаn.

Pristup 1: DFS (Stack metoda)

Ideja:

1. Obilazimo graf pomoću DFS-a
2. Čvor dodajemo TEK nakon svih njegovih suseda
3. Na kraju obrćemo redosled

#include <bits/stdc++.h>
using namespace std;

// Lista susedstva: g[u] sadrži sve čvorove v takve da postoji grana u → v
vector<vector<int>> g;

// state:
// 0 = čvor nije posećen
// 1 = čvor je trenutno u DFS rekurziji (na steku)
// 2 = čvor je potpuno obrađen
vector<int> state;

vector<int> st; // rezultat (topološki poredak, obrnut tokom građenja)

// DFS funkcija vraća false ako detektuje ciklus
bool dfs(int u){

    // Označavamo da smo ušli u čvor u (počeli obradu)
    state[u] = 1;

    // Prolazimo kroz sve susede
    for(int v : g[u]){

        // Ako sused još nije posećen
        if(state[v] == 0){
            // Rekurzivno ga obilazimo
            if(!dfs(v)) return false; // ako dole postoji ciklus → prekid
        }

        // Ako je sused VEĆ u obradi → ciklus!
        else if(state[v] == 1){
            // Ovo znači:
            // u → v, ali je v već na DFS putanji
            // dakle postoji put v → ... → u
            // → zatvorili smo krug
            return false;
        }

        // Ako je state[v] == 2 → već završen → sve ok
    }

    // Završili smo sve susede → sada možemo dodati u
    state[u] = 2;

    // Dodajemo ga u rezultat
    // (biće obrnut redosled, zato kasnije radimo reverse)
    st.push_back(u);

    return true;
}

int main(){
    int n, m; 
    cin >> n >> m;

    g.resize(n);
    state.assign(n, 0);

    // Učitavanje grana
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b; // a → b
        g[a].push_back(b);
    }

    // Pokrećemo DFS iz svakog čvora (zbog nepovezanog grafa)
    for(int i = 0; i < n; i++){
        if(state[i] == 0){
            if(!dfs(i)){
                cout << "Graf ima ciklus - nema topoloskog poretka!";
                return 0;
            }
        }
    }

    // Obrćemo jer smo dodavali "posle obrade"
    reverse(st.begin(), st.end());

    // Ispis rezultata
    for(int x : st) cout << x << " ";
}

Konkretan primer BEZ ciklusa

n = 4
grane:
0 → 1
0 → 2
1 → 3
2 → 3

Tok DFS-a:

dfs(0)
 → dfs(1)
   → dfs(3)
     → dodaj 3
   → dodaj 1
 → dfs(2)
   → 3 već završen
   → dodaj 2
 → dodaj 0

st = [3, 1, 2, 0] → posle reverse → 0 2 1 3

Konkretan primer SA ciklusom

n = 3
grane:
0 → 1
1 → 2
2 → 0

Tok DFS-a:

dfs(0)
 → dfs(1)
   → dfs(2)
     → pokušavamo da idemo u 0
     → state[0] = 1 (još uvek u obradi!)
     → DETEKTOVAN CIKLUS

Program prekida i ispisuje:

Graf ima ciklus - nema topoloskog poretka!

Zašto običan DFS (sa visited) NIJE dovoljan?

Ako koristimo samo visited, onda:

• ne razlikujemo da li je čvor završen
• ili je još u toku obrade

To dovodi do greške:

0 → 1 → 2 → 0

Običan DFS kaže:

"0 je već posećen → ignoriši"

Ali to je pogrešno jer:

0 još NIJE završen → to je ciklus!

Suština (najvažnije za zapamtiti)

✔ Čvor dodajemo tek nakon svih njegovih zavisnosti

✔ state = 1 znači: "nalazimo se trenutno u ovom čvoru"

✔ Ako ponovo naiđemo na state = 1 → ciklus

✔ Ako postoji ciklus → topološki poredak NE postoji

✔ reverse je potreban jer dodajemo čvor POSLE obrade

Pristup 2: Kahn-ov algoritam (BFS)

Ovaj pristup prirodno detektuje ciklus i često je intuitivniji za početnike.

Osnovna ideja: uvek biramo čvor koji nema nijednu zavisnost (in-degree = 0).

Zadatak

Dato je N čvorova i M usmerenih grana. Svaka grana a → b znači da čvor a mora biti obrađen pre čvora b.

Potrebno je odrediti jedan redosled svih čvorova tako da su svi uslovi zadovoljeni.

Ako takav redosled ne postoji (zbog ciklusa), ispisati:

Graf ima ciklus!

Ulaz:

• Prva linija: n m
• Sledećih m linija: parovi a b

Izlaz:

• Ispisati jedan validan redosled čvorova
• Ili poruku da postoji ciklus

#include <bits/stdc++.h>
using namespace std;

int main(){

    int n, m;
    cin >> n >> m;

    // Lista susedstva: g[u] = svi v takvi da postoji u → v
    vector<vector<int>> g(n);

    // indeg[v] = broj grana koje ulaze u čvor v
    vector<int> indeg(n, 0);

    // Učitavanje grafa
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b; // a → b

        g[a].push_back(b);

        // povećavamo broj ulaznih grana za čvor b
        indeg[b]++;
    }

    queue<int> q;

    // U red ubacujemo sve čvorove koji nemaju zavisnosti
    for(int i = 0; i < n; i++){
        if(indeg[i] == 0){
            q.push(i);
        }
    }

    vector<int> order; // konačan topološki poredak

    // Glavna petlja (BFS stil)
    while(!q.empty()){

        // Uzimamo čvor koji nema zavisnosti
        int u = q.front();
        q.pop();

        // Dodajemo ga u rezultat
        order.push_back(u);

        // "Uklanjamo" čvor u iz grafa
        // tj. smanjujemo indegree njegovim susedima
        for(int v : g[u]){

            indeg[v]--;

            // Ako neki sused više nema ulaznih grana
            // znači da su sve njegove zavisnosti rešene
            if(indeg[v] == 0){
                q.push(v);
            }
        }
    }

    // Ako nismo obradili sve čvorove → postoji ciklus
    if(order.size() != n){
        cout << "Graf ima ciklus!";
        return 0;
    }

    // Ispis topološkog poretka
    for(int x : order) cout << x << " ";
}

Konkretan primer (bez ciklusa)

n = 6
grane:
0 → 2
1 → 2
1 → 3
2 → 4
3 → 4
4 → 5

Vizuelni prikaz grafa:

    0       1
     \     / \
      \   /   \
       v v     v
        2       3
         \     /
          v   v
            4
            |
            v
            5

Početni in-degree:

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

Početni red (queue):

q = [0, 1]

Koraci algoritma:

vadimo 0 → order = [0]
  indeg[2] = 1

vadimo 1 → order = [0, 1]
  indeg[2] = 0 → ubacujemo
  indeg[3] = 0 → ubacujemo

q = [2, 3]

vadimo 2 → order = [0, 1, 2]
  indeg[4] = 1

vadimo 3 → order = [0, 1, 2, 3]
  indeg[4] = 0 → ubacujemo

vadimo 4 → order = [0, 1, 2, 3, 4]
  indeg[5] = 0 → ubacujemo

vadimo 5 → order = [0, 1, 2, 3, 4, 5]

Jedan validan topološki poredak:
0 1 2 3 4 5

Primer sa ciklusom

n = 3
grane:
0 → 1
1 → 2
2 → 0

Vizuelni prikaz cikličnog grafa:

0 → 1
↑    |
|    v
2 ←--

in-degree:

0: 1
1: 1
2: 1

Početni red (queue):

q = []

Nijedan čvor nema indegree = 0 → algoritam ne može da počne.

order = []

Pošto:

order.size() != n

zaključujemo: graf ima ciklus i nema validnog topološkog poretka.

Suština Kahn algoritma

✔ Uvek biramo čvor bez zavisnosti (indegree = 0)

✔ Svakim korakom "uklanjamo" čvor iz grafa

✔ Ako na kraju ostanu čvorovi → oni su u ciklusu

✔ Ako na početku nema nijednog čvora sa indegree = 0 → sigurno postoji ciklus

Intuicija (najvažnije)

Zamisli zadatke:

• neki zadaci nemaju preduslove → njih radimo prve
• kada ih završimo → otključavaju se novi zadaci

Ako u nekom trenutku:

nema nijednog zadatka bez preduslova

→ znači da se zadaci međusobno čekaju → ciklus

Objašnjenje osnovne ideje

Rečenica: "uvek biramo čvor koji nema nijednu zavisnost (in-degree = 0)" znači sledeće:

Ako za neki čvor v važi da u njega ne ulazi nijedna grana, to znači da:

• ništa ne mora da se uradi pre njega
• nema preduslova
• možemo odmah da ga obradimo

Zato takve čvorove stavljamo u red i obrađujemo prve.

Kada obradimo neki čvor u, mi ga praktično "uklanjamo" iz grafa:

• smanjujemo broj ulaznih grana njegovim susedima
• time možda otključavamo nove čvorove

Na primer, imamo modul čiji su preduslovi prikazani ulazom:

0 → 2
1 → 2

Vizuelni prikaz grafa sa strelicama:

  0     1
   \   /
    \ /
     2

Čvor 2 ima dva preduslova (0 i 1), pa ne može odmah. Ali 0 i 1 nemaju preduslova → mogu odmah da se obrade.

Koraci:
1) Obrađujemo 0 i 1
2) Sada 2 više nema ulaznih grana → može se obraditi

Ako u nekom trenutku:

ne postoji nijedan čvor sa indegree = 0

to znači da:

svi preostali čvorovi zavise jedni od drugih → postoji ciklus

Realan zadatak (gde se ovo koristi)

Radiš na sistemu za kompajliranje softverskog projekta.

Projekat se sastoji od N modula. Neki moduli zavise od drugih — da bi se modul B kompajlirao, mora prvo da se kompajlira modul A.

Dati su svi odnosi zavisnosti u obliku parova A B.

Zadatak:

Odredi redosled kompajliranja svih modula tako da su sve zavisnosti ispoštovane.

Ako to nije moguće (zbog kružne zavisnosti), ispisati:

GRESKA: ciklicna zavisnost

Primer:

Ulaz:
5 4
0 2
1 2
2 3
3 4

Vizuelni prikaz grafa:

0     1
 \   /
  \ /
   2
   |
   3
   |
   4

Objašnjenje:

• 0 i 1 nemaju zavisnosti → mogu prvi
• nakon njih → 2
• zatim 3
• pa 4

Jedan validan izlaz:

0 1 2 3 4

Primer sa greškom:

3 3
0 1
1 2
2 0

Vizuelni prikaz ciklusa:

0 → 1 → 2
↑         |
|_________|

Ovde postoji kružna zavisnost → nijedan modul ne može prvi, nema rešenja.

Suština (u jednoj rečenici)

Radimo samo ono što trenutno nema preduslove — i tako postepeno otključavamo ostalo.

Vizuelno objašnjenje topološkog sortiranja

Topološko sortiranje određuje redosled izvršavanja čvorova u usmerenom acikličnom grafu (DAG).

Za svaku granu u → v mora važiti da se čvor u nalazi pre čvora v u konačnom redosledu.

Primer grafa:

      0
     / \
    v   v
    1   2
     \ /
      v
      3
      |
      v
      4

Značenje grana:

• 0 mora biti pre 1
• 0 mora biti pre 2
• 1 mora biti pre 3
• 2 mora biti pre 3
• 3 mora biti pre 4

Jedan mogući topološki redosled je:

0 → 1 → 2 → 3 → 4

Ali postoji i drugi validan redosled:

0 → 2 → 1 → 3 → 4

Važno je razumeti da topološko sortiranje često ima više validnih rešenja.

Kahn algoritam – korak po korak

Kahn algoritam koristi niz indegree, koji označava koliko ulaznih grana ima svaki čvor.

• Čvorovi sa indegree = 0 nemaju zavisnosti
• Takvi čvorovi mogu odmah da se izvrše

Za prethodni graf indegree vrednosti su:

Čvor:      0 1 2 3 4
indegree:  0 1 1 2 1

Algoritam počinje od čvorova koji imaju indegree = 0.

Tabela izvršavanja Kahn algoritma (sa objašnjenjima)

Korak	Izvađen čvor	Stanje reda (queue)	Indegree niz	Objašnjenje
Početak	-	[0]	[0,1,1,2,1]	Početak algoritma, biramo čvorove sa indegree = 0 (0 nema preduslova)
1	0	[1,2]	[0,1,0,2,1]	Uklonili smo 0; smanjili indegree čvora 2 sa 1 na 0 → čvor 2 je sada spreman
2	1	[2]	[0,0,0,1,1]	Uklonili smo 1; smanjili indegree čvora 3 sa 2 na 1 → čvor 3 još nije spreman
3	2	[3]	[0,0,0,0,1]	Uklonili smo 2; smanjili indegree čvora 3 sa 1 na 0 → čvor 3 je sada spreman
4	3	[4]	[0,0,0,0,0]	Uklonili smo 3; smanjili indegree čvora 4 sa 1 na 0 → čvor 4 je sada spreman
5	4	[]	[0,0,0,0,0]	Uklonili smo 4; red je prazan → svi čvorovi obrađeni, dobijen topološki poredak

Redosled uklanjanja čvorova iz reda daje topološki poredak grafa:

U ovom primeru dobijamo:

0 → 1 → 2 → 3 → 4

Složenost algoritma

Neka je:

• V – broj čvorova
• E – broj grana

Složenost oba pristupa je ista:

• DFS topološko sortiranje: O(V + E)
• Kahn algoritam: O(V + E)

To znači da se svaki čvor i svaka grana obrađuju najviše jednom.

Primer praktične primene

Jedna od najčešćih primena topološkog sortiranja je planiranje zadataka koji imaju međuzavisnosti.

Primer: predmeti na fakultetu.

Matematika → Algoritmi
Programiranje → Algoritmi
Algoritmi → Veštačka inteligencija

Topološko sortiranje daje redosled u kome se predmeti mogu polagati:

Matematika → Programiranje → Algoritmi → Veštačka inteligencija

Ako bi postojala zavisnost koja pravi ciklus, na primer:

Algoritmi → Matematika

tada topološko sortiranje nije moguće, jer bi svaki predmet zahtevao drugi kao preduslov.

Zadaci za vežbu — Topološko sortiranje

1. Topološko sortiranje pomoću DFS

Tekst zadatka

Dat je usmeren aciklični graf (DAG). Potrebno je pronaći topološki redosled čvorova koristeći DFS algoritam.

Primer

Graf:
0 → 1
0 → 2
1 → 3
2 → 3
3 → 4

Mogući izlaz:
0 2 1 3 4

Prikaži uputstvo

Uputstvo

• Pokreni DFS za svaki čvor koji još nije posećen.
• Nakon što DFS obradi sve susede čvora, dodaj taj čvor u stek.
• Na kraju isprazni stek – to daje topološki redosled.

Prikaži rešenje

// Topološko sortiranje pomoću DFS

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> graf;
vector<bool> posecen;
stack<int> st;

// DFS funkcija
void dfs(int v){

    posecen[v] = true;

    // prolazimo kroz susede
    for(int u : graf[v]){
        if(!posecen[u])
            dfs(u);
    }

    // čvor dodajemo u stek tek
    // nakon što su svi njegovi susedi obrađeni
    st.push(v);
}

int main(){

    int n = 5;

    graf.resize(n);
    posecen.assign(n,false);

    graf[0] = {1,2};
    graf[1] = {3};
    graf[2] = {3};
    graf[3] = {4};

    // DFS pokrećemo za svaki čvor
    for(int i = 0; i < n; i++)
        if(!posecen[i])
            dfs(i);

    // ispis topološkog reda
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
}

2. Topološko sortiranje — Kahn algoritam

Tekst zadatka

Dat je usmeren graf. Pronaći topološki redosled koristeći Kahn algoritam (BFS pristup).

Primer

Graf:
0 → 1
0 → 2
1 → 3
2 → 3

Mogući izlaz:
0 1 2 3

Prikaži uputstvo

Uputstvo

• Izračunaj indegree za svaki čvor.
• U red ubaci sve čvorove koji imaju indegree = 0.
• Ukloni čvor iz reda i smanji indegree njegovih suseda.
• Ako neki sused dobije indegree 0, ubaci ga u red.

Prikaži rešenje

// Kahn algoritam za topološko sortiranje (BFS pristup)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){

    int n = 4; // broj čvorova

    // Lista susedstva: graf[u] = svi v takvi da postoji u → v
    vector<vector<int>> graf(n);

    // indegree[v] = broj ulaznih grana u čvor v
    vector<int> indegree(n, 0);

    // Definicija grafa:
    // 0 → 1
    // 0 → 2
    // 1 → 3
    // 2 → 3
    graf[0] = {1,2};
    graf[1] = {3};
    graf[2] = {3};
    // graf[3] nema izlaznih grana

    // -----------------------------
    // 1. Računamo indegree niz
    // -----------------------------
    for(int i = 0; i < n; i++){
        for(int u : graf[i]){
            indegree[u]++; // svaka grana i → u povećava indegree[u]
        }
    }

    queue<int> q;

    // -----------------------------
    // 2. U red ubacujemo čvorove
    //    bez ulaznih grana
    // -----------------------------
    for(int i = 0; i < n; i++){
        if(indegree[i] == 0){
            q.push(i); // čvor nema preduslova
        }
    }

    vector<int> order; // konačan topološki poredak

    // -----------------------------
    // 3. Glavna petlja (BFS stil)
    // -----------------------------
    while(!q.empty()){

        int v = q.front();
        q.pop();

        // dodajemo čvor u rezultat
        order.push_back(v);

        // "uklanjamo" čvor v iz grafa
        for(int u : graf[v]){

            indegree[u]--; // smanjujemo broj zavisnosti

            // ako više nema zavisnosti → spreman za obradu
            if(indegree[u] == 0){
                q.push(u);
            }
        }
    }

    // -----------------------------
    // 4. Provera ciklusa
    // -----------------------------
    if(order.size() != n){
        cout << "GRESKA: graf ima ciklus!";
        return 0;
    }

    // -----------------------------
    // 5. Ispis topološkog poretka
    // -----------------------------
    for(int x : order){
        cout << x << " ";
    }
}

3. Detekcija ciklusa pomoću topološkog sortiranja

Tekst zadatka

Dat je usmeren graf. Proveriti da li graf sadrži ciklus.

Ako graf ima ciklus, topološko sortiranje nije moguće.

Prikaži uputstvo

Uputstvo

• Primeni Kahn algoritam.
• Prebroj koliko čvorova je obrađeno.
• Ako je broj obrađenih čvorova manji od n, graf sadrži ciklus.

Prikaži rešenje

// Detekcija ciklusa pomoću Kahn algoritma

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){

    int n = 3;

    vector<vector<int>> graf(n);
    vector<int> indegree(n,0);

    graf[0] = {1};
    graf[1] = {2};
    graf[2] = {0}; // pravi ciklus

    for(int i = 0; i < n; i++){
        for(int u : graf[i])
            indegree[u]++;
    }

    queue<int> q;

    for(int i = 0; i < n; i++)
        if(indegree[i] == 0)
            q.push(i);

    int cnt = 0;

    while(!q.empty()){

        int v = q.front();
        q.pop();

        cnt++;

        for(int u : graf[v]){

            indegree[u]--;

            if(indegree[u] == 0)
                q.push(u);
        }
    }

    if(cnt == n)
        cout << "Graf nema ciklus";
    else
        cout << "Graf sadrzi ciklus";
}

4. Planiranje projekata (Topološko sortiranje)

Tekst zadatka

Veliki projekat sastoji se od N zadataka. Neki zadaci moraju biti završeni pre nego što drugi mogu da počnu. Te zavisnosti predstavljene su kao usmeren graf.

Potrebno je pronaći redosled izvršavanja zadataka tako da se poštuju sve zavisnosti.

Primer

Ulaz:
6 6
1 3
2 3
3 4
3 5
4 6
5 6

Izlaz:
1 2 3 4 5 6

Prikaži uputstvo

Uputstvo

• Graf predstavlja zavisnosti između zadataka.
• Potrebno je izvršiti topološko sortiranje.
• Čvorovi sa indegree = 0 mogu se izvršiti prvi.
• Koristi Kahn algoritam.

Prikaži rešenje

Rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
int indegree[100];

int main(){

    int N, M;
    cin >> N >> M;

    // učitavanje grana (zavisnosti)
    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        indegree[b]++;
    }

    queue<int> q;

    // svi zadaci bez preduslova
    for(int i = 1; i <= N; i++){
        if(indegree[i] == 0)
            q.push(i);
    }

    while(!q.empty()){

        int v = q.front();
        q.pop();

        cout << v << " ";

        // uklanjamo grane iz grafa
        for(int sused : graf[v]){

            indegree[sused]--;

            if(indegree[sused] == 0)
                q.push(sused);
        }
    }
}

5. Otkrivanje ciklusa u sistemu zavisnosti

Tekst zadatka

U sistemu softverskih modula neki moduli zavise od drugih. Ako postoji ciklus zavisnosti, sistem ne može da se kompajlira.

Potrebno je proveriti da li graf zavisnosti sadrži ciklus.

Primer

Ulaz:
3 3
1 2
2 3
3 1

Izlaz:
CIKLUS

Prikaži uputstvo

Uputstvo

• Primeni Kahn algoritam.
• Prebroj koliko čvorova je obrađeno.
• Ako je broj obrađenih čvorova manji od N, graf sadrži ciklus.

Prikaži rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
int indegree[100];

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        indegree[b]++;
    }

    queue<int> q;

    for(int i = 1; i <= N; i++){
        if(indegree[i] == 0)
            q.push(i);
    }

    int cnt = 0;

    while(!q.empty()){

        int v = q.front();
        q.pop();

        cnt++;

        for(int sused : graf[v]){

            indegree[sused]--;

            if(indegree[sused] == 0)
                q.push(sused);
        }
    }

    if(cnt == N)
        cout << "NEMA CIKLUSA";
    else
        cout << "CIKLUS";
}

6. Najranije vreme završetka projekta

Tekst zadatka

Projekat se sastoji od N zadataka. Svaki zadatak ima vreme trajanja. Neki zadaci mogu početi tek nakon završetka drugih.

Potrebno je izračunati minimalno vreme završetka celog projekta.

Primer

Zadaci:
1 (3 dana)
2 (2 dana)
3 (4 dana)

Zavisnosti:
1 → 3
2 → 3

Izlaz:
7

Zadatak 3 može početi tek kada se završe zadaci 1 i 2. Najranije vreme početka je max(3,2) = 3. Ukupno vreme = 3 + 4 = 7.

Prikaži uputstvo

Uputstvo

• Koristi topološko sortiranje.
• Za svaki čvor vodi niz dp[v] koji označava najranije vreme završetka tog zadatka.
• Kada prelazimo preko grane u → v važi:
• dp[v] = max(dp[v], dp[u] + trajanje[v])

Prikaži rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
int indegree[100];
int trajanje[100];
int dp[100];

int main(){

    int N, M;
    cin >> N >> M;

    // trajanje zadataka
    for(int i = 1; i <= N; i++)
        cin >> trajanje[i];

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        indegree[b]++;
    }

    queue<int> q;

    for(int i = 1; i <= N; i++){

        if(indegree[i] == 0){

            q.push(i);
            dp[i] = trajanje[i];
        }
    }

    while(!q.empty()){

        int v = q.front();
        q.pop();

        for(int sused : graf[v]){

            dp[sused] = max(dp[sused], dp[v] + trajanje[sused]);

            indegree[sused]--;

            if(indegree[sused] == 0)
                q.push(sused);
        }
    }

    int ans = 0;

    for(int i = 1; i <= N; i++)
        ans = max(ans, dp[i]);

    cout << ans;
}

Napredni zadaci (takmičarski nivo) — BFS i DFS

7. Najudaljeniji čvor u mreži (BFS)

Tekst zadatka

Data je mreža računara predstavljena kao ne-težinski graf. Potrebno je pronaći čvor koji je najudaljeniji od početnog računara S.

Udaljenost između dva računara predstavlja broj kablova (grana) koji se moraju preći.

Ako postoji više takvih čvorova, ispisati bilo koji.

Primer

Ulaz:
6 6
1 2
1 3
2 4
3 5
5 6
4 6

S = 1

Izlaz:
6

Prikaži uputstvo

Uputstvo

• Potrebno je pronaći čvor sa najvećom udaljenošću od čvora S.
• Najbolji način za to je korišćenje BFS algoritma.
• BFS prirodno pronalazi najkraće udaljenosti u ne-težinskom grafu.
• Tokom obilaska vodimo niz dist[v].
• Na kraju prolazimo kroz sve čvorove i pronalazimo najveću vrednost.

Prikaži rešenje

Rešenje (BFS)

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
int distanca[100];

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    int S;
    cin >> S;

    // inicijalizacija udaljenosti
    for(int i = 1; i <= N; i++)
        distanca[i] = -1;

    queue<int> q;

    q.push(S);
    distanca[S] = 0;

    while(!q.empty()){

        int v = q.front();
        q.pop();

        // obilazak svih suseda
        for(int sused : graf[v]){

            if(distanca[sused] == -1){

                distanca[sused] = distanca[v] + 1;
                q.push(sused);
            }
        }
    }

    int najdalji = S;

    // tražimo čvor sa najvećom udaljenošću
    for(int i = 1; i <= N; i++){

        if(distanca[i] > distanca[najdalji]){
            najdalji = i;
        }
    }

    cout << najdalji;
}

8. Broj povezanih komponenti (DFS)

Tekst zadatka

Data je mreža ostrva povezanih mostovima. Svako ostrvo je čvor u grafu, a most je grana.

Potrebno je odrediti koliko postoji odvojenih grupa ostrva, odnosno koliko graf ima povezanih komponenti.

Primer

Ulaz:
7 4
1 2
2 3
4 5
6 7

Izlaz:
3

Prikaži uputstvo

Uputstvo

• Potrebno je pronaći sve povezane komponente grafa.
• Pokrećemo DFS iz svakog neposećenog čvora.
• Svaki put kada pokrenemo novi DFS, otkrili smo novu komponentu.
• Broj pokretanja DFS algoritma jednak je broju komponenti.

Prikaži rešenje

Rešenje (DFS)

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
bool posecen[100];

void dfs(int v){

    posecen[v] = true;

    for(int sused : graf[v]){

        if(!posecen[sused]){
            dfs(sused);
        }
    }
}

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    int brojKomponenti = 0;

    for(int i = 1; i <= N; i++){

        if(!posecen[i]){

            dfs(i);
            brojKomponenti++;
        }
    }

    cout << brojKomponenti;
}

9. Detekcija ciklusa u neusmerenom grafu (DFS)

Tekst zadatka

Potrebno je proveriti da li neusmereni graf sadrži ciklus.

Ciklus postoji ako tokom DFS obilaska naiđemo na već posećen čvor koji nije roditelj trenutnog čvora.

Primer

Ulaz:
4 4
1 2
2 3
3 4
4 2

Izlaz:
DA

Prikaži uputstvo

Uputstvo

• Pokrenuti DFS iz svakog neposećenog čvora.
• Tokom obilaska vodimo informaciju o roditelju čvora.
• Ako naiđemo na već posećen čvor koji nije roditelj, detektovan je ciklus.

Prikaži rešenje

Rešenje (DFS)

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
bool posecen[100];
bool ciklus = false;

void dfs(int v, int roditelj){

    posecen[v] = true;

    for(int sused : graf[v]){

        if(!posecen[sused]){

            dfs(sused, v);
        }
        else if(sused != roditelj){

            // naišli smo na već posećen čvor
            // koji nije roditelj → ciklus
            ciklus = true;
        }
    }
}

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for(int i = 1; i <= N; i++){

        if(!posecen[i]){
            dfs(i, -1);
        }
    }

    if(ciklus)
        cout << "DA";
    else
        cout << "NE";
}

Olimpijski nivo (SIO) — napredni graf algoritmi

10. Najduži put u DAG grafu

Tekst zadatka

Dat je usmereni aciklični graf (DAG). Potrebno je pronaći dužinu najdužeg puta od čvora S do svih ostalih čvorova.

Pošto graf nema cikluse, problem se može rešiti pomoću topološkog sortiranja i dinamičkog programiranja.

Primer

Ulaz:
6 6
1 2
1 3
2 4
3 4
4 5
5 6

S = 1

Prikaži uputstvo

Uputstvo

• Prvo izvršiti topološko sortiranje grafa.
• Zatim prolaziti kroz čvorove tim redosledom.
• Koristiti niz dp[v] koji čuva dužinu najdužeg puta do čvora.
• Za svaku granu u → v ažurirati:
• dp[v] = max(dp[v], dp[u] + 1)

Prikaži rešenje

Rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
bool posecen[100];
stack<int> topo;

void dfs(int v){

    posecen[v] = true;

    for(int sused : graf[v]){

        if(!posecen[sused]){
            dfs(sused);
        }
    }

    // čvor dodajemo u stack
    // nakon obilaska svih suseda
    topo.push(v);
}

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
    }

    int S;
    cin >> S;

    for(int i = 1; i <= N; i++){
        if(!posecen[i])
            dfs(i);
    }

    vector<int> dp(N+1, -1);
    dp[S] = 0;

    while(!topo.empty()){

        int v = topo.top();
        topo.pop();

        if(dp[v] != -1){

            for(int sused : graf[v]){

                dp[sused] = max(dp[sused], dp[v] + 1);
            }
        }
    }

    for(int i = 1; i <= N; i++)
        cout << dp[i] << " ";
}

11. Mostovi u grafu (Bridges)

Tekst zadatka

U mreži puteva neki putevi su kritični. Ako se takav put ukloni, graf postaje nepovezan.

Takve grane nazivamo mostovi (bridges). Potrebno je pronaći sve mostove u grafu.

Primer

Ulaz:
5 5
1 2
2 3
3 4
2 4
4 5

Prikaži uputstvo

Uputstvo

• Koristi se DFS sa vremenima ulaska u čvor.
• Za svaki čvor vodimo:
• tin[v] – vreme ulaska u čvor (kada ga prvi put posećujemo)
• low[v] – najmanje vreme (najraniji čvor) do kog možemo doći iz v koristeći DFS stablo ili povratne grane
• Intuicija:
• Ako iz podstabla čvora to možemo da se vratimo nazad (do v ili nekog ranije posećenog čvora), onda postoji alternativni put → grana nije most

Primer (nije most):

1 — 2
 \  |
  \ |
    3

Postoji ciklus: iz 3 možemo nazad do 1 → postoji alternativni put. Zato nijedna grana ovde nije most.

• Ako ne postoji takav povratak, onda je ta grana jedina veza između delova grafa → most

Primer (most):

1 — 2 — 3

Ako uklonimo granu 2–3, čvor 3 ostaje odsečen. Ne postoji alternativni put → to je most.

• Ako važi:
• low[to] > tin[v]
• onda iz čvora to ne možemo da se vratimo do v ili nekog njegovog prethodnika → grana v–to je most

Prikaži rešenje

Rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
bool posecen[100];
int tin[100], low[100];
int timer = 0;

void dfs(int v, int roditelj){

    posecen[v] = true;

    tin[v] = low[v] = ++timer;

    for(int to : graf[v]){

        if(to == roditelj)
            continue;

        if(posecen[to]){

            low[v] = min(low[v], tin[to]);
        }
        else{

            dfs(to, v);

            low[v] = min(low[v], low[to]);

            if(low[to] > tin[v]){

                cout << "Most: " << v << " - " << to << endl;
            }
        }
    }
}

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for(int i = 1; i <= N; i++){

        if(!posecen[i])
            dfs(i, -1);
    }
}

12. Artikulacione tačke

Tekst zadatka

U komunikacionoj mreži neke tačke su kritične. Ako se takva tačka ukloni, mreža se raspada na više komponenti.

Takvi čvorovi se nazivaju artikulacione tačke.

Primer

Ulaz:
5 5
1 2
2 3
3 4
2 4
4 5

Prikaži uputstvo

Uputstvo

• Takođe se koristi Tarjan DFS algoritam.
• Ako postoji dete to za koje važi:
• low[to] ≥ tin[v]
• onda je v artikulaciona tačka.
• Poseban slučaj je koren DFS stabla.

Prikaži rešenje

Rešenje

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
bool posecen[100];
bool art[100];

int tin[100], low[100];
int timer = 0;

void dfs(int v, int roditelj){

    posecen[v] = true;

    tin[v] = low[v] = ++timer;

    int children = 0;

    for(int to : graf[v]){

        if(to == roditelj)
            continue;

        if(posecen[to]){

            low[v] = min(low[v], tin[to]);
        }
        else{

            dfs(to, v);

            low[v] = min(low[v], low[to]);

            if(low[to] >= tin[v] && roditelj != -1)
                art[v] = true;

            children++;
        }
    }

    if(roditelj == -1 && children > 1)
        art[v] = true;
}

int main(){

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){

        int a, b;
        cin >> a >> b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for(int i = 1; i <= N; i++){

        if(!posecen[i])
            dfs(i, -1);
    }

    for(int i = 1; i <= N; i++)
        if(art[i])
            cout << i << " ";
}

Vraćanje na lekciju

← Mapa učenja — Grafovi i stabla