Tare conexitate

Intuiția

Într-un graf neorientat ne întrebam doar dacă totul e „legat” — conexitate. La un graf orientat, muchiile au sens, deci a ajunge din u în v NU mai garantează că ajungi și din v în u. Un graf orientat e tare conex dacă pentru orice pereche de noduri (u, v) există drum u → v ȘI drum v → u. Pe scurt: din oriunde ajungi oriunde, respectând sensul.

Vezi cum funcționează

Pornește animația și urmărește cum nodurile se grupează în componente tare conexe (CTC): insule de noduri din care toate ajung reciproc unele la altele. Graful întreg e tare conex exact când există o singură astfel de insulă. Animația rulează algoritmul lui Kosaraju — îl vei diseca în capitolul de parcurgeri; aici concentrează-te pe rezultat: fiecare culoare = o insulă.

Algoritmul pas cu pas

Fie graful orientat cu 4 noduri și muchiile: 1→2, 2→3, 3→1, 1→4. Nodurile 1, 2, 3 formează un circuit; nodul 4 primește o muchie, dar din el nu iese nimic.

Pasul 1 — circuitul 1→2→3→1. Verifică perechile una câte una: 1→2 direct și înapoi 2→3→1; 2→3 direct și înapoi 3→1→2; 1→2→3 dus și 3→1 întors. Între oricare două dintre {1, 2, 3} există drum dus-întors: ele sunt în aceeași CTC.

Pasul 2 — nodul 4. Ajung din 1 în 4 (muchia 1→4), dar din 4 nu iese nicio muchie, deci NU există drum 4 → 1. Drumul trebuie să existe în ambele sensuri; aici lipsește întoarcerea. Așadar 4 NU intră în CTC-ul lui {1, 2, 3} — formează singur componenta B (o CTC perfect validă de un singur nod).

Concluzie. Avem 2 componente tare conexe, nu una singură. Prin urmare graful NU e tare conex — exact pentru că 4 e o „fundătură”. Dacă am adăuga muchia 4→1, atunci 4 ar putea reveni la circuit și totul ar deveni o singură CTC.

Implementare C++

Pentru un simplu test „da/nu” nu construim toate CTC. Folosim observația: graful e tare conex dacă, pornind dintr-un nod fixat (nodul 0), ajung peste tot în graful normal ȘI ajung peste tot în graful transpus (cu toate muchiile întoarse). Primul DFS verifică 0 → orice; al doilea verifică orice → 0. Împreună: între orice u și v am drum u → 0 → v și retur.

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

int n;                          // numar de noduri (0..n-1)
vector<int> graf[100], transp[100];   // graful normal si cel transpus
bool vizitat[100];

// DFS clasic care marcheaza toate nodurile atinse din 'nod'
void dfs(vector<int> g[], int nod) {
    vizitat[nod] = true;
    for (int vecin : g[nod]) {
        if (!vizitat[vecin]) {
            dfs(g, vecin);
        }
    }
}

// true daca toate nodurile sunt atinse dintr-un DFS pornit din 0
bool toateAtinse(vector<int> g[]) {
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }
    dfs(g, 0);
    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            return false;       // nodul i nu a fost atins
        }
    }
    return true;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;          // muchie orientata a -> b
        graf[a].push_back(b);
        transp[b].push_back(a); // in transpus, muchia merge invers
    }

    // tare conex daca din 0 ajung peste tot SI in transpus la fel
    bool tareConex = toateAtinse(graf) && toateAtinse(transp);

    cout << (tareConex ? "tare conex" : "NU e tare conex") << "\n";
    // exemplul lectiei renumerotat 0..3 (muchii 0->1, 1->2, 2->0, 0->3):
    // primul DFS atinge tot, dar in transpus DFS din 0 NU atinge nodul 3
    // (adica in graful original 3 nu ajunge la 0) => NU e tare conex
    return 0;
}

Complexitate

Fiecare DFS vizitează fiecare nod o dată și parcurge fiecare muchie o dată, deci O(n+m). Două DFS-uri rămân O(n+m) — un salt uriaș față de O(n²·(n+m)) al abordării naive.