Introduction aux Ensembles Disjoints

La structure de données Union-Find (ou ensembles disjoints) est un type abstrait de données arborescent conçu pour gérer efficacement une collection de partitions. Elle prend en charge deux opérations fondamentales de manière optimale :

• Union : Fusionner deux ensembles distincts en un seul.
• Find : Déterminer si deux éléments appartiennent au même ensemble.

Représentation et Logique de Base

Chaque ensemble est représenté par une arborescence où la racine sert d'identifiant unique pour l'ensemble. Un tableau, souvent appelé parent, est utilisé pour stocker le parent de chaque nœud. Initialement, chaque élément est sa propre racine, ce qui signifie que chaque nœud forme son propre arbre isolé.

Pour fusionner les ensembles contenant les éléments a et b, on trouve leurs racines respectives et on fait pointer la racine de l'un vers la racine de l'autre. Si les deux racines sont identiques, les éléments sont déjà dans le même ensemble.

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int find_root(int node) {
    if (parent[node] != node) {
        return find_root(parent[node]);
    }
    return node;
}

void union_sets(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_b] = root_a;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_elements, num_queries;
    if (!(cin >> num_elements >> num_queries)) return 0;

    parent.resize(num_elements + 1);
    for (int i = 1; i <= num_elements; ++i) {
        parent[i] = i;
    }

    while (num_queries--) {
        int operation, u, v;
        cin >> operation >> u >> v;
        if (operation == 1) {
            union_sets(u, v);
        } else {
            cout << (find_root(u) == find_root(v) ? "Oui" : "Non") << "\n";
        }
    }
    return 0;
}

Optimisation par Compression de Chemin

L'implémentation naive peut souffrir de dégénérescence. Si les unions successives forment une longue chaîne linéaire, l'opération find_root nécessitera un temps d'exécution linéaire $O(N)$, ce qui entraîne un dépassement de temps (Time Limit Exceeded) sur de grands jeux de données.

Pour résoudre ce problème, on applique la compression de chemin. Lors de la recherche de la racine d'un nœud, on modifie directement le pointeur de chaque nœud visité pour qu'il pointe vers la racine. Cela aplatit la structure de l'arbre et garantit que les recherches futures seront quasi constantes.

Cette optimisation s'applique de manière paresseuse : seuls les nœuds traversés lors d'une requête find sont mis à jour. Les nœuds qui ne sont jamais interrogés n'ont pas besoin d'être optimisés immédiatement.

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int find_root(int node) {
    // Compression de chemin : le parent devient directement la racine
    if (parent[node] != node) {
        parent[node] = find_root(parent[node]);
    }
    return parent[node];
}

void union_sets(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_b] = root_a;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_elements, num_queries;
    if (!(cin >> num_elements >> num_queries)) return 0;

    parent.resize(num_elements + 1);
    for (int i = 1; i <= num_elements; ++i) {
        parent[i] = i;
    }

    while (num_queries--) {
        int operation, u, v;
        cin >> operation >> u >> v;
        if (operation == 1) {
            union_sets(u, v);
        } else {
            cout << (find_root(u) == find_root(v) ? "Oui" : "Non") << "\n";
        }
    }
    return 0;
}