Operații cu mulțimi

De ce contează?

Două cluburi au liste de membri. Vrei să afli: cine e în măcar unul (reuniune), cine e în amândouă (intersecție), cine e doar în primul (diferență). Dacă bifezi membrii pe o listă comună, răspunzi la toate trei dintr-o singură trecere.

Mulțimi prin vectori caracteristici

O mulțime de valori întregi mici se reprezintă perfect cu un vector caracteristic: A[x] = 1 dacă x e în mulțime. Operațiile pe mulțimi devin atunci operații simple, poziție cu poziție:

Operație	Simbol	Regula pe car.	Sens
reuniune	A ∪ B	`A[x] \|\| B[x]`	în măcar una
intersecție	A ∩ B	`A[x] && B[x]`	în ambele
diferență	A \ B	`A[x] && !B[x]`	în A, nu în B

Algoritm pas cu pas

A = , B = . Vectorii caracteristici aliniați:

A	0	1	1	0	1	0
val	0	1	2	3	4	5

Vectorul caracteristic al lui A = {1, 2, 4}.

B	0	0	1	0	1	1
val	0	1	2	3	4	5

Vectorul caracteristic al lui B = {2, 4, 5}. Aplici operația pe fiecare coloană față de A.

Rezultate: A ∪ B = , A ∩ B = , A \ B = .

Implementare C++

#include <iostream>
using namespace std;

int main() {
    const int V = 1000;
    bool A[V + 1] = {false}, B[V + 1] = {false};

    int n, m, x;
    cin >> n;
    for (int i = 0; i < n; i++) { cin >> x; A[x] = true; }
    cin >> m;
    for (int i = 0; i < m; i++) { cin >> x; B[x] = true; }

    cout << "Reuniune: ";
    for (int x = 0; x <= V; x++) if (A[x] || B[x]) cout << x << " ";
    cout << "\nIntersectie: ";
    for (int x = 0; x <= V; x++) if (A[x] && B[x]) cout << x << " ";
    cout << "\nDiferenta A\\B: ";
    for (int x = 0; x <= V; x++) if (A[x] && !B[x]) cout << x << " ";
    cout << "\n";
    return 0;
}

Observația-cheie

Parcurgi intervalul de valori o singură dată per operație și rezultatul iese automat în ordine crescătoare. Fără vectori caracteristici, ai compara fiecare element din A cu fiecare din B — O(n·m) în loc de O(V).

Complexitate

Metodă	Timp	Spațiu
cu vectori caracteristici	O(n + m + V)	O(V)
comparare directă A vs B	O(n · m)	O(1)

Câștigi când V (intervalul de valori) e rezonabil. Pentru valori uriașe, folosești set.

Greșeli frecvente

Capcane reale la operațiile cu mulțimi:

Confuzi reuniunea cu intersecția: reuniune = SAU (||), intersecție = ȘI (&&). Inversarea dă rezultatul opus.
Diferența nesimetrică: A \ B ≠ B \ A. A[x] && !B[x] e altceva decât B[x] && !A[x].
Interval prea mic: valorile depășesc dimensiunea vectorilor → acces în afară. Dimensionează după valoarea maximă.
Comparare O(n·m) inutilă: pe valori mici, vectorii caracteristici sunt mult mai rapizi decât a încrucișa cele două liste.

Vizualizare

Vizualizarea de mulțime/dicționar arată apartenența și combinarea elementelor:

Indiciu

Gândește fiecare operație ca pe o regulă aplicată coloană cu coloană: reuniunea aprinde coloana dacă e aprinsă în oricare, intersecția doar dacă e aprinsă în amândouă.

De reținut

Mulțimi mici = vectori caracteristici; reuniune = ||, intersecție = &&, diferență = && !.
O singură parcurgere a intervalului de valori → rezultat ordonat, O(n + m + V).
Diferența e nesimetrică (A \ B ≠ B \ A); pentru valori uriașe folosește set.