Componente tare conexe: algoritmul Kosaraju

O componentă tare conexă a unui graf orientat este o mulțime maximală de vârfuri între care există drumuri în ambele sensuri. Accesibilitatea într-un singur sens nu este suficientă. Algoritmul Kosaraju găsește componentele prin două parcurgeri DFS și inversarea sensurilor arcelor.

Dacă reducem fiecare componentă la un singur vârf, graful componentelor nu are circuite. Altfel, componentele aflate pe un circuit ar fi reciproc accesibile și ar forma de fapt o singură componentă.

Cum funcționează

Prima parcurgere DFS se face pe graful inițial. Adăugăm un vârf în order după ce i-am terminat toți descendenții, nu când îl descoperim. Dacă graful nu este accesibil integral din primul start, continuăm din fiecare vârf încă nevizitat. Astfel obținem o ordine de finalizare pentru toate vârfurile.

A doua etapă parcurge graful transpus, în care fiecare arc x→y devine y→x. Pornim în ordinea inversă a finalizărilor. Fiecare DFS nou primește o etichetă nouă și marchează o componentă tare conexă. În reprezentarea prin matrice, nu trebuie să construim fizic o a doua matrice: citim a[y][x] când căutăm succesorii lui x în transpus.

Programul presupune 1 <= n <= 100 și capete de arc valide. Recursia are cel mult o sută de niveluri în acest exemplu. Pentru grafuri mari, o implementare iterativă trebuie să păstreze corect momentul de finalizare, nu doar ordinea scoaterii dintr-o stivă simplă. Aceasta este o diferență importantă față de marcarea elementară a accesibilității.

Exemplu urmărit pas cu pas

Pentru arcele 1→2, 2→1 și 2→3, vârfurile 1 și 2 formează o componentă, iar 3 formează alta. Din 1 ajungem în 3, dar nu există drum de întoarcere din 3 către 1.

Prima parcurgere care începe în 1 finalizează mai întâi 3, apoi 2, apoi 1. Pe transpus, pornirea din 1 găsește 1 și 2 fără să pătrundă în componenta lui 3. Următoarea pornire neetichetată identifică vârful 3. Numerele etichetelor sunt convenționale; importante sunt grupurile de vârfuri cu etichetă comună.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int n, a[101][101] = {}, order[101], count = 0, label[101] = {};
bool seen[101] = {};
void first(int x) {
    seen[x] = true;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !seen[y])
            first(y);
    order[count++] = x;
}
void second(int x, int id) {
    label[x] = id;
    for (int y = 1; y <= n; ++y)
        if (a[y][x] && !label[y])
            second(y, id);
}
int main() {
    int m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = 1;
    }
    for (int x = 1; x <= n; ++x)
        if (!seen[x])
            first(x);
    int components = 0;
    for (int i = count - 1; i >= 0; --i)
        if (!label[order[i]])
            second(order[i], ++components);
    std::cout << components << '\n';
    for (int x = 1; x <= n; ++x)
        std::cout << label[x] << (x == n ? '\n' : ' ');
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n, count = 0;
std::vector<std::vector<int>> a(101, std::vector<int>(101, 0));
std::vector<int> order(101), label(101, 0);
std::vector<char> seen(101, 0);
void first(int x) {
    seen[x] = true;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !seen[y])
            first(y);
    order[count++] = x;
}
void second(int x, int id) {
    label[x] = id;
    for (int y = 1; y <= n; ++y)
        if (a[y][x] && !label[y])
            second(y, id);
}
int main() {
    int m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = 1;
    }
    for (int x = 1; x <= n; ++x)
        if (!seen[x])
            first(x);
    int components = 0;
    for (int i = count - 1; i >= 0; --i)
        if (!label[order[i]])
            second(order[i], ++components);
    std::cout << components << '\n';
    for (int x = 1; x <= n; ++x)
        std::cout << label[x] << (x == n ? '\n' : ' ');
}

De ce funcționează și cât costă

Ordinea descrescătoare a finalizărilor selectează o componentă care nu poate scăpa în componente încă neprelucrate prin arcele transpuse. În interiorul ei, accesibilitatea reciprocă rămâne valabilă și după transpunere. Repetarea separă astfel exact componentele grafului condensat.

Cu matrice, cele două parcurgeri costă O(n²) timp și reprezentarea O(n²) memorie. Cu liste pentru graf și transpus, timpul și memoria sunt O(n+m). Vectorii de ordine și etichete ocupă O(n).

Greșeli frecvente

Nu păstra ordinea descoperirii în locul finalizării. Nu executa a doua etapă pe graful inițial. Nu folosi componentele unui graf neorientat obținut prin ignorarea sensurilor: acestea răspund unei întrebări diferite.

Exersează

Ce se schimbă dacă adaugi arcul 3→1 în exemplul lecției?

Rezolvare explicată: Toate cele trei vârfuri devin reciproc accesibile. Din 3 ajungem în 1 și apoi în 2, iar din 1 și 2 ajungem în 3. Rezultă o singură componentă.

Continuă să înveți

DFS, grafuri orientate și componente conexe.

Întrebări frecvente

Ce înseamnă tare conex?

Din fiecare vârf poți ajunge în oricare altul respectând sensul arcelor. Condiția cere accesibilitate reciprocă pentru toate perechile din componentă.

De ce un vârf izolat este o componentă?

El formează singur o mulțime maximală în care condiția de accesibilitate reciprocă este satisfăcută prin convenția drumului vid.

De ce inversăm arcele?

Transpunerea păstrează componentele tare conexe, dar inversează legăturile dintre ele. Împreună cu ordinea de finalizare, permite izolarea componentelor pe rând.

Contează valoarea numerică a etichetei?

De regulă, nu. Două vârfuri aparțin aceleiași componente dacă etichetele coincid. Dacă enunțul cere o ordine specială, rezultatul trebuie prelucrat corespunzător.

Kosaraju este singurul algoritm posibil?

Nu. Există și Tarjan și alte abordări. Fiecare are propriile invariante; nu amesteca regulile stivei Tarjan cu cele două parcurgeri Kosaraju.