L'Union-Find est une structure de données efficace pour gérer des ensembles disjoints, souvent utilisée pour modéliser des relatoins entre éléments. Dans cet article, nous explorons son application à deux problèmes classiques : la détermination du nombre maximum de héros dans un scénario de vérité et de mensonge, et la vérification de relations dans une chaîne alimentaire.

Problème des héros et des vilains

Dans un scénario hypothétique, chaque personne est soit un héros (dit la vérité), soit un vilain (ment sur l'identité des autres). Étant donné n personnes et m déclarations, nous devons calculer le nombre maximum possible de héros. Si une contradiction est détectée, nous retournons -1.

La solution utilise l'Union-Find avec un ensemble étendu : pour chaque personne i, nous créons deux nœuds : i (représentant la condition d'être vilain) et i+n (représentant la condition d'être héros). Lorsqu'une personne x déclare que y est bon, nous unissons les nœuds correspondants pour refléter la cohérence des conditions.

#include <bits/stdc++.h>
using namespace std;

const int MAX_PEOPLE = 1e6 + 5;
int parent[MAX_PEOPLE * 2];
int set_size[MAX_PEOPLE * 2];
int num_people, num_statements, max_heroes;

int fast_read() {
    int value = 0, sign = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + ch - '0';
        ch = getchar();
    }
    return value * sign;
}

int find_root(int node) {
    if (parent[node] != node) {
        int root = find_root(parent[node]);
        set_size[root] += set_size[node];
        set_size[node] = 0;
        parent[node] = root;
    }
    return parent[node];
}

void merge_sets(int node_x, int node_y) {
    int root_x = find_root(node_x);
    int root_y = find_root(node_y);
    if (root_x != root_y) {
        set_size[root_x] += set_size[root_y];
        set_size[root_y] = 0;
        parent[root_y] = root_x;
    }
}

int main() {
    num_people = fast_read();
    num_statements = fast_read();
    max_heroes = 0;

    // Initialisation des ensembles disjoints pour les deux conditions par personne
    for (int i = 1; i <= 2 * num_people; i++) {
        parent[i] = i;
    }
    for (int i = 1; i <= num_people; i++) {
        set_size[i] = 0;
    }
    for (int i = num_people + 1; i <= 2 * num_people; i++) {
        set_size[i] = 1;
    }

    // Traitement des déclarations
    for (int i = 0; i < num_statements; i++) {
        int person_a = fast_read();
        int person_b = fast_read();
        string declaration;
        cin >> declaration;

        int root_a_vilain = find_root(person_a);
        int root_b_vilain = find_root(person_b);
        int root_a_hero = find_root(person_a + num_people);
        int root_b_hero = find_root(person_b + num_people);

        if (declaration == "bon") {
            merge_sets(person_a, person_b);
            merge_sets(person_a + num_people, person_b + num_people);
        } else {
            merge_sets(person_a + num_people, person_b);
            merge_sets(person_b + num_people, person_a);
        }
    }

    // Vérification des contradictions et calcul de la réponse
    for (int i = 1; i <= num_people; i++) {
        if (find_root(i) == find_root(i + num_people)) {
            cout << -1 << endl;
            return 0;
        }
        max_heroes += max(set_size[find_root(i)], set_size[find_root(i + num_people)]);
        set_size[find_root(i)] = set_size[find_root(i + num_people)] = 0;
    }
    cout << max_heroes << endl;
    return 0;
}

Problème de la chaîne alimentaire

Dans un écosystème, les relations entre espèces sont modélisées : chaque espèce a une relation avec elle-même, sa proie et son prédateur. Étant donné n espèces et k déclarations, nous devons compter les déclarations fausses basées sur ces relations prédéfinies.

La solution utilise l'Union-Find avec trois nœuds par espèce : x pour l'espèce elle-même, x+n pour sa proie, et x+2n pour son prédateur. Les déclarations de type 1 (même espèce) et de type 2 (relation prédateur-proie) sont validées en vérifiant la cohérence des ensembles.

#include <cstdio>

const int MAX_SPECIES = 300005;
int parent[MAX_SPECIES];
int num_species, num_statements, false_count;

inline int fast_input() {
    int sum = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        sum = sum * 10 + ch - 48;
        ch = getchar();
    }
    return sum;
}

int find_set(int element) {
    if (parent[element] != element) {
        parent[element] = find_set(parent[element]);
    }
    return parent[element];
}

void union_sets(int x, int y) {
    int root_x = find_set(parent[x]);
    int root_y = find_set(parent[y]);
    parent[root_x] = root_y;
}

int main() {
    int x, y, z;
    num_species = fast_input();
    num_statements = fast_input();
    false_count = 0;

    // Initialisation : trois nœuds par espèce pour les relations
    for (int i = 1; i <= 3 * num_species; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < num_statements; i++) {
        z = fast_input();
        x = fast_input();
        y = fast_input();

        if (x > num_species || y > num_species) {
            false_count++;
            continue;
        }

        if (z == 1) {
            // Déclaration de même espèce
            if (find_set(x + num_species) == find_set(y) || find_set(x + 2 * num_species) == find_set(y)) {
                false_count++;
                continue;
            }
            union_sets(x, y);
            union_sets(x + num_species, y + num_species);
            union_sets(x + 2 * num_species, y + 2 * num_species);
        } else if (z == 2) {
            // Déclaration de relation prédateur-proie
            if (x == y) {
                false_count++;
                continue;
            }
            if (find_set(x) == find_set(y) || find_set(x + 2 * num_species) == find_set(y)) {
                false_count++;
                continue;
            }
            union_sets(x, y + 2 * num_species);
            union_sets(x + num_species, y);
            union_sets(x + 2 * num_species, y + num_species);
        }
    }

    printf("%d\n", false_count);
    return 0;
}

Ces exemples illustrent comment l'Union-Find peut être adapté pour modéliser des relations logiques et vérifier la cohérence dans des scénarios complexes.