Ce que la structure refuse de faire

1. Oui, en $O(1)$, et gratuitement. On ajoute un champ classes initialisé à $n$ et décrémenté exactement lorsqu'une union a lieu :

let unir u x y =
  let a = trouver u x and b = trouver u y in
  if a = b then false                      (* deja unis : on ne compte pas *)
  else begin ...; u.classes <- u.classes - 1; true end

L'invariant est : u.classes est le nombre de racines de la forêt. Il tient parce qu'une union effective supprime exactement une racine. Noter que unir doit rendre un booléen : sans lui, l'appelant ne saurait pas si le compteur a bougé. C'est ce que fait le true/false de la version du chapitre chap:unir, et Kruskal s'en sert.

2. Non, pas en mieux que $\Theta (n)$. Les liens vont des fils vers la racine : depuis un élément on sait remonter, jamais descendre. Pour énumérer une classe il faut balayer les $n$ éléments et retenir ceux dont trouver rend le représentant voulu. Maintenir en plus la liste des éléments de chaque classe est possible, mais rend unir linéaire en la taille de la plus petite classe : on retombe sur la première mise en œuvre naïve.

3. Non, tant qu'on compresse. La compression de chemin réécrit des cases dont rien ne garde trace ; annuler l'union ne les remettrait pas en place. Le problème « Unir & trouver avec annulation » construit une variante qui sait annuler, et montre par la mesure ce que la compression y casse.

Ce que l'exercice illustre : la pauvreté du contrat n'est pas un oubli. Chacune des trois demandes ci-dessus, si on l'exigeait, ferait perdre ce qui fait la valeur de la structure.