 |
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
|
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
#include <tpl_union.H>
Relación binaria de eqivalencia entre enteros. (Quick Union problem)
Relation implementa una relación binaria entre elementos enteros.
El algoritmo usado es el llamado Quick weithed fast union.
Completamente inspirado de Sedgewick & Wayne, Algorithms, 4th edition.
Esta clase es de muy alto desempeño. Aunque teóricamente sus operaciones son O(lg n), en la práctica tienden a ser O(1) en tiempo amortizado.
La cantidad de enteros n se especifica en el constructor de la clase. Los elementos a relacionarse deben estar comprendidos entre 0 y n-1. La operaciones no validan si el entero es válido.
Si la cantidad de enteros es desconocida, entonces úsese la clase Relation. Si se requiere relacionar elementos de otros tipos, entonces úsese Relation_T