Choose your language!

---

|

SCC — Komponente jake povezanosti (Kosaraju i Tarjan)

Komponente jake povezanosti (eng. Strongly Connected Components — SCC) su ključni koncept za analizu usmerenih grafova.

SCC predstavlja podskup čvorova gde je svaki čvor dostupan iz svakog drugog. To znači da za čvorove u istoj SCC vredi:

u → v i v → u (postoje putanje u oba smera)

Ova struktura je posebno važna u:

• kompajlerima (analiza zavisnosti)
• profesionalnim sistemima (tarife, mreže, strujanje podataka)
• teoriji igara i grafovima stanja
• web grafovima (PageRank, fragmentacija mreže)

Čvorovi iste boje pripadaju istoj komponenti jake povezanosti (SCC).

Primer grafa

   (1) → (2) → (3)
    ↑     ↓      ↑
    |     ↑      |
    |     |      |
   (5) ← (4) ← (6)

Grane u grafu:

1 → 2
2 → 3
2 → 4
4 → 2
4 → 5
5 → 1
6 → 4
6 → 3

SCC (Strongly Connected Components) grupe su:

• {1,2,4,5}
• {3}
• {6}

Na prvi pogled može delovati da je dovoljno da čvorovi formiraju ciklus da bi činili SCC, ali definicija je stroža.

Komponenta jake povezanosti je maksimalan skup čvorova takav da za svaka dva čvora u i v iz tog skupa postoje putanje u oba smera:

u → v

i

v → u

Reč maksimalan znači da u tu grupu ne možemo dodati nijedan novi čvor, a da i dalje važi da su svi čvorovi međusobno dostupni jedni iz drugih.

U ovom primeru čvorovi:

1 → 2 → 4 → 5 → 1

čine ciklus, ali to nije jedini razlog zbog kog su u istoj SCC. Važno je da iz svakog od ovih čvorova možemo stići do svakog drugog i vratiti se nazad. Zato oni zajedno čine jednu jaku komponentu:

{1,2,4,5}

Zašto čvor 3 nije u toj grupi?

Do čvora 3 možemo stići, na primer, preko:

2 → 3

ali iz čvora 3 ne postoji putanja nazad do čvorova 1, 2, 4 ili 5. Zbog toga čvor 3 mora da ostane u posebnoj SCC:

{3}

Slično tome, čvor 6 takođe ne može da se vrati ni iz jednog drugog čvora. Iako iz njega možemo stići do:

6 → 4
6 → 3

ne postoji putanja kojom bismo iz drugih čvorova mogli da se vratimo do 6. Zato je i on zasebna SCC:

{6}

Važno je naglasiti da SCC nije isto što i običan ciklus.

Na primer, skup:

{1,2}

nije SCC, iako su 1 i 2 deo većeg ciklusa. Razlog je što možemo dodati još čvorova, kao što su 4 i 5, i i dalje bi važilo da se svi međusobno mogu dostići. Zato SCC mora da bude najveći mogući takav skup.

Drugim rečima, SCC je najveća grupa čvorova u kojoj svaki čvor može da stigne do svakog drugog čvora i da se vrati nazad.

Vizuelni prikaz SCC grupa u primeru grafa. Svaka boja predstavlja jednu komponentu jake povezanosti.

Kosaraju algoritam — ideja

Posmatrajmo graf iz prethodnog primera:

   (1) → (2) → (3)
    ↑     ↓      ↑
    |     ↑      |
    |     |      |
   (5) ← (4) ← (6)

Njegove SCC komponente su:

{1,2,4,5}
{3}
{6}

Kosaraju algoritam pronalazi ove komponente koristeći dva DFS prolaza:

1. DFS po originalnom grafu i beleženje redosleda završavanja čvorova
2. Transponovanje (obrtanje) svih grana
3. DFS po transponovanom grafu u obrnutom redosledu završavanja

Ključna ideja algoritma nije samo DFS, već upravo redosled u kojem se čvorovi obrađuju u drugom prolazu.

U prvom DFS-u čvor se ne dodaje u listu order kada ga prvi put posetimo, već tek kada završimo obradu svih njegovih suseda. Zato lista order predstavlja redosled završavanja DFS-a.

Jedan mogući tok prvog DFS prolaza

DFS kreće iz čvora 1:

1 → 2 → 3

Čvor 3 nema neposetene susede,
pa završava prvi.

Vraćamo se na 2.

2 → 4 → 5

Čvor 5 završava.
Zatim završava 4.
Zatim završava 2.
Zatim završava 1.

Čvor 6 još nije posećen,
pa pokrećemo novi DFS iz 6.

Jedan mogući redosled završavanja je:

order = [3,5,4,2,1,6]

Napomena: tačan redosled DFS obilaska može da zavisi od redosleda suseda u listi susedstva, ali princip rada algoritma ostaje isti.

U drugom prolazu čvorove obrađujemo obrnutim redosledom:

reversed(order)

[6,1,2,4,5,3]

Pre drugog DFS-a pravimo transponovani graf.

Ako je u originalnom grafu postojala grana:

u → v

u transponovanom grafu ona postaje:

v → u

Dakle, svi smerovi grana se obrću.

Zašto je ovo korisno?

Ako svaku SCC komponentu posmatramo kao jedan „super-čvor“, dobijamo graf koji se naziva SCC DAG. Taj graf nema cikluse.

Prvi DFS nam daje redosled po kojem treba da krenemo u drugom prolazu. Kada u transponovanom grafu krenemo od prvog neposećenog čvora iz reversed(order), DFS ostaje unutar jedne SCC komponente i ne preliva se u druge komponente.

Za naš primer, jedan mogući redosled izdvajanja komponenti je:

{6}
{1,2,4,5}
{3}

Na kraju dobijamo iste SCC grupe:

{1,2,4,5}
{3}
{6}

Važno je naglasiti da je redosled ispisa SCC komponenti nebitan. Bitno je samo da su komponente pravilno izdvojene. Algoritam može prvo ispisati {6}, pa {1,2,4,5}, pa {3}, ili neki drugi redosled, u zavisnosti od redosleda obilaska.

Upravo zato Kosaraju koristi dva DFS prolaza: prvi određuje pravilan redosled obrade, a drugi u transponovanom grafu izdvaja jednu po jednu SCC komponentu.

Kosaraju algoritam kroz tri koraka: DFS završavanja, transponovanje grafa i izdvajanje SCC komponenti.

Kosaraju — C++ implementacija

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

// ------------------------------------------------------------
// g  = originalni usmereni graf
// gt = transponovani graf
//
// Ako u originalnom grafu postoji:
//
// u → v
//
// onda u transponovanom postoji:
//
// v → u
// ------------------------------------------------------------

vector<vector<int>> g, gt;

// ------------------------------------------------------------
// used[v]
// = da li je čvor već posećen tokom DFS-a
// ------------------------------------------------------------

vector<bool> used;

// ------------------------------------------------------------
// order
// čuva redosled završavanja DFS-a
//
// Čvor se dodaje TEK kada DFS završi njegovu obradu.
//
// Ovo je ključna ideja Kosaraju algoritma.
// ------------------------------------------------------------

vector<int> order;

// ------------------------------------------------------------
// comp
// trenutna SCC komponenta
// ------------------------------------------------------------

vector<int> comp;


// ============================================================
// PRVI DFS
// ============================================================
//
// DFS po ORIGINALNOM grafu.
//
// Cilj:
// odrediti redosled završavanja čvorova.
//
// Kada završimo obradu čvora,
// dodajemo ga u vector "order".
//
// Čvorovi koji završavaju kasnije
// biće obrađeni ranije u drugom DFS-u.
// ============================================================

void dfs1(int v){

    // označavamo čvor kao posećen
    used[v] = true;

    // prolazimo kroz sve susede
    for(int to : g[v]){

        // DFS samo ako sused nije posećen
        if(!used[to])
            dfs1(to);
    }

    // --------------------------------------------------------
    // OVO JE NAJVAŽNIJI DEO
    // --------------------------------------------------------
    //
    // Čvor dodajemo TEK nakon završetka DFS-a.
    //
    // To znači:
    //
    // svi čvorovi dostupni iz v
    // već su obrađeni.
    //
    // Zato order predstavlja:
    //
    // "redosled izlaska iz DFS-a"
    // --------------------------------------------------------

    order.push_back(v);
}


// ============================================================
// DRUGI DFS
// ============================================================
//
// DFS po TRANSPONOVANOM grafu.
//
// Kada krenemo iz odgovarajućeg čvora,
// obići ćemo tačno jednu SCC komponentu.
//
// Sve posećene čvorove dodajemo u "comp".
// ============================================================

void dfs2(int v){

    used[v] = true;

    // dodajemo čvor u trenutnu SCC komponentu
    comp.push_back(v);

    // DFS po transponovanom grafu
    for(int to : gt[v]){

        if(!used[to])
            dfs2(to);
    }
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // --------------------------------------------------------
    // Kreiramo grafove veličine n
    // --------------------------------------------------------

    g.assign(n, {});
    gt.assign(n, {});
    used.assign(n, false);

    // --------------------------------------------------------
    // Učitavanje grana
    // --------------------------------------------------------
    //
    // Ulaz:
    //
    // a b
    //
    // znači:
    //
    // a → b
    //
    // U transponovanom grafu:
    //
    // b → a
    // --------------------------------------------------------

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

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

        // prelazak na 0-based indeksiranje
        --a;
        --b;

        // originalni graf
        g[a].push_back(b);

        // transponovani graf
        gt[b].push_back(a);
    }


    // ========================================================
    // PRVI DFS
    // ========================================================
    //
    // Radimo DFS iz svih nepovezanih komponenti.
    //
    // Cilj:
    // popuniti vector "order".
    // ========================================================

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

        if(!used[i])
            dfs1(i);
    }


    // ========================================================
    // RESET visited niza
    // ========================================================

    fill(used.begin(), used.end(), false);


    // ========================================================
    // DRUGI DFS
    // ========================================================
    //
    // Čvorove obrađujemo:
    //
    // obrnutim redosledom iz "order"
    //
    // Zašto?
    //
    // SCC DAG ima osobinu da će
    // "izlazne" komponente završavati kasnije.
    //
    // Obradom od kraja garantujemo
    // da svaki DFS uhvati tačno jednu SCC.
    // ========================================================

    for(int i = n - 1; i >= 0; i--){

        int v = order[i];

        // ako čvor nije posećen,
        // pronalazimo novu SCC komponentu
        if(!used[v]){

            // praznimo trenutnu komponentu
            comp.clear();

            // DFS po transponovanom grafu
            dfs2(v);

            // ------------------------------------------------
            // Ispis SCC komponente
            // ------------------------------------------------

            cout << "SCC: ";

            for(int x : comp)
                cout << x + 1 << " ";

            cout << "\n";
        }
    }
}

Ako listu order posmatramo kao stek, čvor koji poslednji završi DFS nalaziće se na vrhu steka.

order = [3,5,4,2,1,6]

Vrh steka
    6
    1
    2
    4
    5
    3
Dno steka

Kosaraju — Python varijanta

from collections import defaultdict

g  = defaultdict(list)
gt = defaultdict(list)
order = []
visited = set()

def dfs1(v):
    visited.add(v)
    for to in g[v]:
        if to not in visited:
            dfs1(to)
    order.append(v)

def dfs2(v, comp):
    visited.add(v)
    comp.append(v)
    for to in gt[v]:
        if to not in visited:
            dfs2(to, comp)

n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    gt[b].append(a)

for i in range(1, n+1):
    if i not in visited:
        dfs1(i)

visited.clear()

for v in reversed(order):
    if v not in visited:
        comp = []
        dfs2(v, comp)
        print("SCC:", comp)

Tarjanov algoritam — jedan DFS

Tarjan je efikasniji: koristi jedan DFS i low-link vrednosti, slično kao kod detekcije mostova i artikulacionih tačaka.

Drži stek čvorova koji su trenutno aktivni u pretrazi. Kad se pronađe koren SCC-a, skida sve elemente te komponente sa steka.

vector<int> tin, low, st;
vector<bool> onStack;
int timer = 0;

void dfs_tarjan(int v){
    tin[v] = low[v] = ++timer;
    st.push_back(v);
    onStack[v] = true;

    for(int to : g[v]){
        if(!tin[to]){
            dfs_tarjan(to);
            low[v] = min(low[v], low[to]);
        }
        else if(onStack[to]){
            low[v] = min(low[v], tin[to]);
        }
    }

    if(tin[v] == low[v]){
        cout << "SCC: ";
        while(true){
            int node = st.back(); st.pop_back();
            onStack[node] = false;
            cout << node+1 << " ";
            if(node == v) break;
        }
        cout << "\n";
    }
}

Vizualizacija Tarjanovog algoritma (low-link)

DFS stablo sa tin i low vrednostima koje Tarjan koristi za pronalaženje SCC komponenti.

tin:  1  2  3  4  5
low:  1  1  3  3  1
stack: [1,2,5,4,3]

⬇️ kada DFS završi 3 i low[3] == tin[3]
SCC je (3,4,5,2,1)

Ovo se dešava zato što se vraćamo DFS parentima koji su deo ciklusa.

Vraćanje na vodič za oblast "Grafovi i stabla"

← Mapa učenja — Grafovi i stabla

Zašto su SCC važne u takmičarskom programiranju?

Na prvi pogled SCC može delovati kao „još jedan algoritam za grafove”. Međutim, komponente jake povezanosti predstavljaju jednu od najvažnijih tehnika u naprednom takmičarskom programiranju.

Glavna ideja je:

Kada skupimo cikluse u jednu SCC komponentu, graf se pretvara u DAG.

Reči povezane kružnim zavisnostima formiraju SCC komponente koje se kasnije mogu sabiti u jedan čvor.

To je izuzetno važno jer se mnogi problemi mnogo lakše rešavaju na DAG grafovima nego na opštim usmerenim grafovima.

Intuicija

Ako između više čvorova postoji mogućnost kretanja u oba smera, onda oni praktično predstavljaju jednu „celinu”.

Na primer:

A → B → C
↑       ↓
└───────┘

Iz svakog čvora možemo stići do svakog drugog, pa sva tri čvora pripadaju istoj SCC komponenti.

Umesto da posmatramo:

A, B, C

možemo ih „sabiti” u jedan super-čvor:

[SCC]

Kondenzacioni graf

Kada svaku SCC komponentu zamenimo jednim čvorom, dobijamo novi graf koji se naziva:

condensation graph
(kondenzacioni graf)

Najvažnije svojstvo:

Kondenzacioni graf je uvek DAG.

SCC komponente se sabijaju u super-čvorove. Dobijeni kondenzacioni graf je uvek DAG.

Zašto?

Ako bi postojao ciklus između SCC komponenti, onda bi sve te komponente zapravo činile jednu veću SCC.

Zašto je ovo korisno?

Kada dobijemo DAG:

• možemo raditi topološko sortiranje
• možemo koristiti DP po grafu
• možemo računati broj puteva
• možemo tražiti najduže puteve
• možemo propagirati informacije između komponenti

Zato se SCC često pojavljuje kao:

1. pronađi SCC
2. sabij graf
3. radi DP na DAG-u

Veza sa realnim takmičarskim zadacima

Mnogi teški problemi zapravo imaju skrivene cikluse koji komplikuju rešenje.

SCC omogućava da:

• eliminišemo cikluse
• grupišemo međusobno zavisna stanja
• pojednostavimo graf
• pređemo na mnogo lakši DAG problem

Vrlo čest obrazac:

SCC + DAG + DP

Primer tipičnog zadatka

Zamislimo graf reči:

"zebra" → "rame"
"rame"  → "mera"
"mera"  → "rampa"
"rampa" → "papir"

Ako postoji mogućnost vraćanja između nekih grupa reči, te reči čine SCC komponentu.

Nakon sabijanja SCC komponenti, problem se često svodi na:

• koliko čvorova možemo dosegnuti
• kolika je maksimalna zarada
• koliko postoji puteva
• koji je najduži lanac

Upravo zbog toga SCC predstavlja jedan od temelja naprednih graf algoritama.

Tipična progresija znanja

DFS/BFS
   ↓
Topološko sortiranje
   ↓
DAG DP
   ↓
SCC
   ↓
SCC + DAG + DP

Kada učenik razume SCC, otvara mu se veliki broj ozbiljnih takmičarskih problema.

Zadaci za vežbu

• Odrediti SCC na grafu koji predstavlja zavisnost modula u softveru.
• Primeniti SCC za detekciju cikličnih referenci u bazama podataka.
• Odrediti koliko SCC komponenti postoji i koji su im reprezentanti.
• Napisati program koji redukuje graf na DAG SCC komponenata.

Zadaci za samostalno rešavanje

Zadatak 1: Kaladont — broj dostižnih reči

U igri kaladont formira se niz reči tako da se završni slog prethodne reči poklapa sa početnim slogom naredne reči.

U ovom zadatku, početni slog je definisan kao prva dva karaktera reči, a završni slog kao poslednja dva karaktera.

Dat je rečnik koji sadrži N različitih reči. Za svaku reč potrebno je odrediti koliko različitih reči iz rečnika može da se dosegne ako je ta reč početna.

Drugim rečima, za svaku početnu reč treba prebrojati koliko reči postoji za koje postoji bar jedan validan niz kaladonta koji počinje tom rečju i u kome se ta reč nalazi.

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Na prvi pogled deluje da treba za svaku reč posebno da pokrećemo DFS ili BFS po svim mogućim nastavcima.

To bi bilo presporo ako bismo graf gradili direktno nad svim rečima. Zato je potrebno da problem posmatramo malo drugačije.

---

Ključna ideja

Pošto se porede samo prva i poslednja dva slova, svaku reč možemo opisati kao:

početni slog -> završni slog

Na primer, ako je reč:

zebra

onda je njen opis:

ze -> ra

To znači da je svaka reč usmerena veza između dva sloga.

Tako dobijamo graf u kome su:

• čvorovi = slogovi od dva slova
• grane = reči iz rečnika

---

Zašto je graf mali?

Pošto ima 26 slova engleske abecede, broj mogućih slogova je:

26 * 26 = 676

To je veoma važno zapažanje. Iako može biti do 10^6 reči, broj različitih slogova je mali.

Zato je mnogo bolje raditi nad slogovima nego nad samim rečima.

---

Gde nastaje problem?

U grafu se mogu pojaviti ciklusi. Na primer:

ra -> me
me -> ra

Ako jednom dođemo do jednog od tih slogova, možemo prelaziti između njih i zato ih ne treba posmatrati odvojeno.

Upravo zato koristimo SCC komponente jake povezanosti.

---

Šta radimo sa SCC komponentama?

Sve slogove koji su međusobno dostižni sabijamo u jednu komponentu. Tako dobijamo novi graf u kome su čvorovi SCC komponente.

Taj novi graf nema cikluse, pa je to zapravo DAG.

Ključna ideja:

Najpre sabijamo cikluse u SCC komponente, a zatim na dobijenom DAG grafu računamo koje su komponente dostižne.

---

Zašto običan DP ne radi?

Ne možemo da pišemo:

dp[c] = compWords[c] + suma(dp[dece])

jer ista SCC komponenta može biti dostižna različitim putevima, pa bi bila prebrojana više puta.

Dakle, ovde ne računamo zbir puteva, nego uniju dostižnih komponenti.

---

Kako dobiti odgovor?

Za svaku SCC komponentu računamo skup svih SCC komponenti koje se iz nje mogu dostići. Pošto ima najviše 676 slogova, taj skup možemo čuvati pomoću bitset-a.

Kada znamo koje su komponente dostižne, samo saberemo broj reči u tim komponentama.

Dakle, odgovor za početnu reč dobija se iz SCC komponente njenog početnog sloga, uz malu korekciju za samu početnu reč.

---

Vizuelna intuicija

reči:

zebra  -> ze -> ra
rame   -> ra -> me
mera   -> me -> ra

Ovde imamo ciklus:

ra <-> me

Zato su ra i me u istoj SCC komponenti.

---

Zašto je ovo efikasno?

Umesto da radimo na milion reči, radimo nad najviše 676 slogova.

To znači da možemo:

• izgraditi graf veoma brzo
• pronaći SCC komponente
• sabiti graf u DAG
• računati dostižne komponente pomoću bitset-a

Zbog toga je rešenje veoma brzo i prolazi sve testove.

---

Složenost

O(N + V^2 / 64)

gde je N broj reči u rečniku, a V = 676.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

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

using ll = long long;

const int V = 26 * 26;

/*
    Pretvaranje slogova od dva slova u broj:
    "ab" -> 0 * 26 + 1
*/
int id(char a, char b) {
    return (a - 'a') * 26 + (b - 'a');
}

vector<int> g[V], gt[V];
vector<bool> used;
vector<int> order;
int comp[V];
int compCnt = 0;

/*
    Prvi DFS Kosaraju algoritma.
    Beležimo redosled izlaska iz čvora.
*/
void dfs1(int v) {
    used[v] = true;
    for (int to : g[v]) {
        if (!used[to]) dfs1(to);
    }
    order.push_back(v);
}

/*
    Drugi DFS na transponovanom grafu.
    Formira jednu SCC komponentu.
*/
void dfs2(int v, int c) {
    comp[v] = c;
    for (int to : gt[v]) {
        if (comp[to] == -1) dfs2(to, c);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int,int>> words(n);

    /*
        cnt[v] = broj reči koje počinju slogom v
    */
    vector<int> cnt(V, 0);

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        int pref = id(s[0], s[1]);
        int suf  = id(s[(int)s.size() - 2], s[(int)s.size() - 1]);

        words[i] = {pref, suf};

        /*
            Svaka reč je usmerena grana:
            pref -> suf
        */
        g[pref].push_back(suf);
        gt[suf].push_back(pref);

        /*
            Brojimo koliko reči počinje ovim slogom.
        */
        cnt[pref]++;
    }

    /*
        Kosaraju:
        1) DFS u originalnom grafu
        2) DFS u transponovanom grafu
    */
    used.assign(V, false);
    for (int i = 0; i < V; i++) {
        if (!used[i]) dfs1(i);
    }

    fill(comp, comp + V, -1);
    reverse(order.begin(), order.end());

    for (int v : order) {
        if (comp[v] == -1) {
            dfs2(v, compCnt++);
        }
    }

    /*
        Broj reči u svakoj SCC komponenti.
        To je zbir svih reči koje počinju slogovima
        koji pripadaju toj komponenti.
    */
    vector<ll> compWords(compCnt, 0);
    for (int v = 0; v < V; v++) {
        compWords[comp[v]] += cnt[v];
    }

    /*
        Gradimo DAG SCC komponenti.
    */
    vector<vector<int>> dag(compCnt);
    for (int v = 0; v < V; v++) {
        for (int to : g[v]) {
            int a = comp[v];
            int b = comp[to];
            if (a != b) {
                dag[a].push_back(b);
            }
        }
    }

    for (int i = 0; i < compCnt; i++) {
        sort(dag[i].begin(), dag[i].end());
        dag[i].erase(unique(dag[i].begin(), dag[i].end()), dag[i].end());
    }

    /*
        Topološki redosled SCC DAG-a.
        Pošto je DAG, možemo ga dobiti Kahn-ovim algoritmom.
    */
    vector<int> indeg(compCnt, 0);
    for (int i = 0; i < compCnt; i++) {
        for (int to : dag[i]) indeg[to]++;
    }

    queue<int> q;
    for (int i = 0; i < compCnt; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    vector<int> topo;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (int to : dag[v]) {
            if (--indeg[to] == 0) q.push(to);
        }
    }

    /*
        reach[c]
        = bitset svih SCC komponenti koje su dostižne
          iz SCC komponente c (uključujući i samu c)
    */
    vector<bitset<V>> reach(compCnt);

    /*
        Obrnuti topološki red:
        prvo obrađujemo "duboke" čvorove,
        zatim roditelje.
    */
    for (int idx = compCnt - 1; idx >= 0; idx--) {
        int c = topo[idx];

        reach[c].set(c);

        for (int to : dag[c]) {
            reach[c] |= reach[to];
        }
    }

    /*
        reachWordsCount[c]
        = ukupan broj reči čiji je početni slog
          u nekoj dostižnoj SCC komponenti od c
    */
    vector<ll> reachWordsCount(compCnt, 0);

    for (int c = 0; c < compCnt; c++) {
        ll sum = 0;

        for (int d = 0; d < compCnt; d++) {
            if (reach[c].test(d)) {
                sum += compWords[d];
            }
        }

        reachWordsCount[c] = sum;
    }

    /*
        Za svaku početnu reč:
        - gledamo SCC komponentu njenog završnog sloga
        - saberemo sve reči koje se mogu dosegnuti odatle
        - ako početna reč nije već obuhvaćena tim skupom,
          dodamo 1 za samu početnu reč
    */
    for (auto [pref, suf] : words) {
        int cSuf = comp[suf];
        int cPref = comp[pref];

        ll ans = reachWordsCount[cSuf];

        if (!reach[cSuf].test(cPref)) {
            ans++;
        }

        cout << ans << '\n';
    }

    return 0;
}

Objašnjenje rešenja

Reči ne posmatramo direktno, već preko slogova od dva slova. Tako svaka reč postaje usmerena grana između dva sloga.

Pošto postoji samo 676 mogućih slogova, graf je mali i lako se obrađuje.

Problem nastaje zbog ciklusa. Zato najpre pronalazimo SCC komponente i sabijamo ih u super-čvorove.

Kada to uradimo, dobijamo DAG graf. Na njemu ne sabiramo odgovore po putevima, jer bi došlo do duplog brojanja.

Umesto toga, za svaku komponentu čuvamo skup svih dostižnih komponenti pomoću bitset-a.

Zatim saberemo koliko reči počinje slogovima iz svih tih dostižnih komponenti.

Ako početna reč nije već obuhvaćena tim skupom, dodamo 1 za samu početnu reč.

---

Najvažnija ideja

Najveća optimizacija nije u samom kodu, već u modelovanju problema:

• reči pretvaramo u grane
• slogove pretvaramo u čvorove
• cikluse sabijamo u SCC komponente
• na dobijenom DAG-u računamo uniju dostižnih komponenti

---

Zaključak

Ovo je tipičan olimpijski zadatak u kome je najvažnije prepoznati pravu strukturu grafa.

Kada se problem pravilno prevede na graf slogova, rešenje postaje vrlo elegantno i efikasno.

Zaključak

SCC predstavljaju temelj za sve napredne algoritme u grafovima, uključujući topološko sortiranje, DP po grafu stanja, analizu ciklusa, planiranje zadataka i segmentaciju mreža.

Sledeće preporučeno:
Dinamičko programiranje na DAG-u

---