Componente conexe

Cum numeri bucățile unui graf, cum le etichetezi, și problemele care se reduc la asta fără să spună „graf".

Ideea

O parcurgere pornită dintr-un vârf vizitează exact vârfurile la care se poate ajunge din el, adică o componentă conexă întreagă.

Așa că pornești o parcurgere din primul vârf nevizitat, apoi din următorul, și tot așa. Numărul de porniri este numărul de componente conexe.

int nrc = 0;
for (int i = 1; i <= n; i++)
    if (!vizitat[i]) {
        nrc++;
        df(i);
    }
cout << nrc;

Cu aceste câteva linii rezolvi una dintre cele mai frecvente cerințe de la grafuri.

Etichetarea

De obicei nu vrei doar numărul, ci și din ce componentă face parte fiecare vârf. Schimbarea e mică: în loc de vizitat folosești un vector de etichete.

int comp[101];

void df(int x, int eticheta) {
    comp[x] = eticheta;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && comp[y] == 0)
            df(y, eticheta);
}

int main() {
    ...
    int nrc = 0;
    for (int i = 1; i <= n; i++)
        if (comp[i] == 0)
            df(i, ++nrc);
}

comp[i] == 0 înseamnă „încă nevizitat", pentru că vectorul global pornește cu zerouri. Un singur vector face acum ambele treburi.

Cu etichetele, alte întrebări devin banale:

// sunt x și y în aceeași componentă?
if (comp[x] == comp[y]) cout << "DA";

// dimensiunea fiecărei componente
int dim[101] = {0};
for (int i = 1; i <= n; i++)
    dim[comp[i]]++;

// cea mai mare componentă
int best = 1;
for (int c = 2; c <= nrc; c++)
    if (dim[c] > dim[best]) best = c;

Testul comp[x] == comp[y] este mult mai bun decât o parcurgere separată pentru fiecare întrebare. Etichetezi o dată și răspunzi de câte ori vrei.

Verificarea conexității

Un graf este conex dacă are exact o componentă:

if (nrc == 1) cout << "conex";

Sau, fără să numeri: pornești o parcurgere din vârful 1 și verifici la final dacă au rămas vârfuri nevizitate.

Probleme care sunt grafuri fără să pară

Multe enunțuri nu pomenesc cuvântul „graf". Îți dai seama după o relație între perechi de obiecte și o întrebare despre grupuri sau despre accesibilitate.

„Într-o clasă, unii elevi se cunosc. Câte grupuri de prieteni se formează, dacă prietenii prietenilor sunt și ei în grup?" Vârfuri = elevi, muchii = relația de cunoaștere, răspuns = numărul de componente conexe.

„Se dau orașe legate prin șosele. Câte șosele noi trebuie construite ca să se poată circula între oricare două orașe?" Dacă sunt k componente, răspunsul este k - 1, pentru că fiecare șosea nouă poate uni cel mult două componente.

„Se dă o matrice cu 0 și 1. Câte zone formate din valori de 1 vecine există?" Aici graful este implicit: vârfurile sunt celulele, iar muchiile sunt vecinătățile. Parcurgi la fel, dar în loc de linia din matricea de adiacență te uiți la cei patru (sau opt) vecini:

void umple(int i, int j) {
    if (i < 1 || i > n || j < 1 || j > m) return;   // în afara matricei
    if (a[i][j] != 1) return;                        // nu face parte din zonă
    a[i][j] = 2;                                     // marchez ca vizitat
    umple(i-1, j);
    umple(i+1, j);
    umple(i, j-1);
    umple(i, j+1);
}

Cele două teste de la început asigură toate verificările, așa că nu mai ai nevoie de altele înainte de fiecare apel. Marchezi schimbând valoarea, deci nu îți trebuie un al doilea tablou.

Numărul de zone se află la fel ca numărul de componente:

int zone = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] == 1) {
            zone++;
            umple(i, j);
        }

Un exemplu complet

Se citește un graf neorientat. Să se afișeze numărul de componente conexe și, pentru fiecare, vârfurile din care este formată.

#include <iostream>
using namespace std;

int a[101][101], comp[101], n, m, nrc;

void df(int x) {
    comp[x] = nrc;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && comp[y] == 0)
            df(y);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (comp[i] == 0) {
            nrc++;
            df(i);
        }

    cout << nrc << "\n";
    for (int c = 1; c <= nrc; c++) {
        cout << "componenta " << c << ": ";
        for (int i = 1; i <= n; i++)
            if (comp[i] == c)
                cout << i << " ";
        cout << "\n";
    }

    return 0;
}

Fiecare vârf izolat formează singur o componentă. Așa e corect, dar e ușor de uitat când verifici de mână.

De reținut

• Numărul de porniri ale parcurgerii = numărul de componente conexe.
• Etichetează vârfurile o dată. Apoi comp[x] == comp[y] îți răspunde instantaneu.
• Un vector de etichete înlocuiește vectorul vizitat.
• Ca să unești k componente ai nevoie de k - 1 muchii.
• Zonele dintr-o matrice sunt aceeași problemă, cu vecinătăți în loc de muchii.