Considérons une hiérarchie familiale modélisée par un arbre généalogique. L'objectif est de déterminer, pour chaque niveau de profondeur depuis la racine, le nombre de membres sans enfants (nœuds feuilles).

Spécification d'entrée : Chaque cas de test débute par une ligne contenant deux entiers N et M. N représente le nombre total de nœuds dans l'arbre, et M le nombre de nœuds non-feuilles. Les M lignes suivantes décrivent chaque nœud non-feuille au format : ID K ID[1] ID[2] ... ID[K], où ID est l'identifiant du nœud (un nombre à deux chiffres), K est le nombre de ses enfants, et les ID subséquents sont les identifiants de ces enfants. L'identifiant de la racine est fixé à 01. L'entrée se termine lorsque N vaut 0 ; ce cas ne doit pas être traité.

Spécification de sortie : Pour chaque cas de test, afficher sur une seule ligne le comptage des nœuds feuilles par niveau, en partant de la racine. Les valeurs sont séparées par un espace, sans espace superflu en fin de ligne.

Exemple :

Entrée :

2 1
01 1 02

Sortie :

0 1

Approche algorithmique : On utilise une liste d'adjacence pour représenter l'arbre. Un parcours en largeur (BFS) depuis la racine permet d'assigner les niveaux de profondeur et de compter les feuilles à chaque niveau. Une file (queue) gère les nœuds à visiter, et des tableaux stockent les niveaux et les compteurs de feuilles.

#include <iostream>
#include <vector>
#include <queue>

const int MAX_NODES = 100;

int main() {
    int nb_noeuds, nb_non_feuilles;
    std::cin >> nb_noeuds >> nb_non_feuilles;

    std::vector<std::vector<int>> liste_enfants(MAX_NODES);
    for (int i = 0; i < nb_non_feuilles; ++i) {
        int identifiant, nombre_enfants;
        std::cin >> identifiant >> nombre_enfants;
        for (int j = 0; j < nombre_enfants; ++j) {
            int id_enfant;
            std::cin >> id_enfant;
            liste_enfants[identifiant].push_back(id_enfant);
        }
    }

    if (nb_noeuds == 0) return 0;

    std::vector<int> niveau(MAX_NODES, -1);
    std::queue<int> file_traitement;
    file_traitement.push(1); // Racine correspondant à l'identifiant 01
    niveau[1] = 0;

    std::vector<int> compteur_feuilles(MAX_NODES, 0);
    int profondeur_max = 0;

    while (!file_traitement.empty()) {
        int noeud_courant = file_traitement.front();
        file_traitement.pop();

        if (liste_enfants[noeud_courant].empty()) {
            ++compteur_feuilles[niveau[noeud_courant]];
        }

        for (int enfant : liste_enfants[noeud_courant]) {
            niveau[enfant] = niveau[noeud_courant] + 1;
            file_traitement.push(enfant);
            if (niveau[enfant] > profondeur_max) {
                profondeur_max = niveau[enfant];
            }
        }
    }

    for (int i = 0; i <= profondeur_max; ++i) {
        if (i > 0) std::cout << " ";
        std::cout << compteur_feuilles[i];
    }
    std::cout << std::endl;

    return 0;
}