Numărul de componente tare conexe ale unui graf orientat - metodă cu matricea drumurilor

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 ³ ). 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!