Conexitate

Intuiția

Un graf neorientat se sparge natural în insule: grupuri de noduri în care din oricare ajungi la oricare altul mergând pe muchii. O astfel de insulă maximală se numește componentă conexă. Dacă întreg graful e o singură insulă, spunem că e conex. A „înțelege conexitatea” înseamnă să vezi graful nu ca o grămadă de noduri, ci ca aceste insule separate — și să le poți număra.

Vezi cum funcționează

Pornește animația și urmărește cum o singură parcurgere (DFS) intră într-un nod și „colorează” toată insula din care face parte. Când nu mai are unde să meargă, căutăm următorul nod necolorat și pornim o insulă nouă.

Algoritmul pas cu pas

Fie un graf cu 6 noduri și muchiile 1-2, 2-3, 4-5, 5-6. Se văd două insule: {1,2,3} și {4,5,6}. Ținem un vector comp[] care zice, pentru fiecare nod, în ce componentă a căzut (0 = încă nevizitat). La început totul e 0:

Parcurgem nodurile de la 1. Nodul 1 are comp = 0, deci e nevizitat: pornim prima parcurgere și îi dăm eticheta 1. DFS pleacă din 1, ajunge la 2 (muchia 1-2), apoi la 3 (muchia 2-3) — ordinea de vizitare este 1 → 2 → 3 și toată insula {1,2,3} primește eticheta 1:

Continuăm. Nodurile 2 și 3 au deja comp != 0, le sărim. Următorul nevizitat e 4 (comp = 0): pornim a doua parcurgere, etichetă 2. DFS vizitează 4 → 5 → 6 — insula {4,5,6} primește eticheta 2:

Nodurile 5 și 6 sunt deja vizitate, le sărim. Am terminat: am pornit DFS-ul de 2 ori, deci graful are 2 componente conexe. Cum 2 != 1, graful nu e conex.

Implementare C++

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

int n, m;
vector<int> adj[100005];    // liste de adiacenta
int comp[100005];           // comp[u] = componenta nodului u (0 = nevizitat)

// DFS care eticheteaza toata componenta nodului u cu c
void dfs(int u, int c) {
    comp[u] = c;
    for (int vec : adj[u]) {
        if (comp[vec] == 0) {
            dfs(vec, c);
        }
    }
}

int main() {
    // exemplu: 6 noduri, muchiile 1-2, 2-3, 4-5, 5-6
    n = 6;
    m = 4;
    int E[4][2] = {{1, 2}, {2, 3}, {4, 5}, {5, 6}};
    for (int i = 0; i < m; i++) {
        int a = E[i][0], b = E[i][1];
        adj[a].push_back(b);    // graf neorientat: ambele sensuri
        adj[b].push_back(a);
    }

    int componente = 0;
    for (int u = 1; u <= n; u++) {
        if (comp[u] == 0) {         // insula noua, inca neexplorata
            componente++;           // o noua pornire = o noua componenta
            dfs(u, componente);     // eticheteaza toata insula lui u
        }
    }

    cout << "Componente conexe: " << componente << "\n";   // 2
    if (componente == 1) {
        cout << "Graful este conex\n";
    } else {
        cout << "Graful NU este conex\n";                  // se afiseaza asta
    }
    return 0;
}

Pe exemplul nostru: dfs(1, 1) etichetează {1,2,3} cu 1, apoi dfs(4, 2) etichetează {4,5,6} cu 2 — exact vectorul comp = [1,1,1,2,2,2] din trace-ul de mai sus. Contorul ajunge la 2, deci graful nu e conex. Bonus: comp[] răspunde instant la întrebarea „sunt u și v în aceeași insulă?” — comp[u] == comp[v].

Complexitate

Fiecare nod e vizitat o singură dată (comp[u] != 0 îl blochează la a doua întâlnire), iar fiecare muchie e parcursă de două ori în total (o dată din fiecare capăt) — de aici O(n+m), indiferent câte porniri de DFS faci: parcurgerile nu se suprapun, ci își împart graful. Spațiul O(n) vine din vectorul comp[] și din stiva recursiei.