Se me ocurre dividir el conjunto de tarjetas en dos, computar las clases de equivalencia recursivamente en las dos mitades y después comparar un representante de cada clase de equivalencia entre las dos mitades. El problema es que en el peor caso, el último paso podría llevar O(n2) si todas las clases de equivalencia tienen un único elemento. Tampoco se me ocurre una forma de descartar clases de equivalencia, porque podría pasar que una clase de equivalencia de tarjetas de tamaño k = n/2 + 1 que nos interesa, tenga k - 1 tarjetas en una mitad y 1 en la otra mitad (en la primera división en mitades).
No se si se entiende el problema, pero igual no se me ocurre cómo hacerlo.