Union-find

Extrait.

En informatique, union-find est une structure de données qui représente une partition d’un ensemble fini (ou de manière équivalente une relation d’équivalence). Elle a essentiellement deux opérations trouver et unir et est appelée union-find, suivant en cela la terminologie anglo-saxonne : Find (trouver) : détermine la classe d’équivalence d’un élément ; elle sert ainsi à déterminer si deux éléments appartiennent à la même classe d’équivalence ; Union (unir) : réunit deux classes d’équivalence en une seule.