Introducere
În cadrul acestui articol îmi propun să demonstrez o variantă diferită de rezolvare a problemei #Tare conexitate , fără algoritmii prezentați în secțiunea „Tare conexitate” a resurselor pbInfo (adică nefolosind Plus-Minus sau Kosaraju). În schimb, algoritmul se folosește de algoritmul Roy-Warshall-Floyd, sau mai precis de o variantă de-a sa pentru grafuri neponderate (Matricea drumurilor).
Ce ne cere problema?
Se dă un graf orientat cu n
noduri. Vrem să determinăm numărul de componente tare conexe ale grafului. Vom face asta într-un mod mai ineficient, dar mai uşor de înţeles.
Cum funcționează sursa?
Sursa descrisă în următoarele paragrafe este ~39964733 și se găsește în atașamentul articolului.
Complexitatea timp este de O(n 3 ). n≤100
, deci ne încadrăm în limita alocată. Înainte de a forma matricea drumurilor, vrem să luăm în considerare și „drumurile” de lungime 0 de la fiecare nod la el însuşi, deci setăm diagonala principală a matricei drumurilor la 1. După ce facem algoritmul propriu-zis al matricei drumurilor, ne uităm la aceasta. Observăm că oricare două noduri care se află în aceeaşi componentă tare conexă vor avea rândurile corespunzătoare identice.
De exemplu: în ataşament, nodurile 1
, 2
şi 4
se află în aceeaşi componentă şi rândurile asociate acestora coincid în matricea de drumuri. În schimb, nodurile 6
şi 7
diferă prin faptul că nu se pot accesa reciproc.
Putem observa că am declarat matricea drumuri
cu char, pentru a folosi biblioteca <cstring> atunci când parcurgem rândurile matricei. Procesul de numărare se bazează pe un vector vizitat
, unde vor rămâne setate la 0
doar câte un nod per componentă tare conexă. Astfel, numărul de componente cerute va fi egal cu numărul de elemente egale cu zero.
Mulțumesc pentru atenție!