103 Stacking Boxes
http://acm.uva.es/p/v1/103.html

En este problema, han de caber unas cajas dentro de otras e indicar el numero maximo que caben de estas asi como que cajas concretas forman ese orden.

Este problema tiene un juez especial, asi que si hay mas de una solucion, mientras sea correcta da igual cual pongamos, el juez la valorara correctamente.

Lo primero, es una vez leida una caja, ordenar sus componentes en orden ascendente (las caracteristicas expuestas en el problema, nos permiten permutar las componentes), asi nos sera mas facil comprobar con una sola pasada y de manera lineal, si una caja cabe dentro de otra.

Una vez obtenidas todas las cajas ordenadas, hay que hacer una ordenacion topologica del conjunto de cajas, viendo cuales cajas en las componentes caben entre si o no. En el momento que una caja no cabe en una, ya es mas peque?a.
(Vamos, comprobar una a una cada componente de dos cajas, y en el momento que sean distintas, la que sea menor es mas peque?a).

Estas dos ordenaciones pueden hacerse, por ejemplo, usando la funcion qsort de C.

Asi tendremos el orden topologico. Despues solo tendremos que generar el grafo de que cajas caben en cuales , y recorrerlo con una busqueda en profundidad. Cada caja es digamos un vertice del grafo.

Al buscar, sabremos que solo podemos meternos en cajas que en el orden topologico anterior sean mayores que las nuestras, eliminando asi elementos en la busqueda en profundidad. (Digamos sabemos que la caja en orden 3, solo quizas pueda meterse en las cajas 4, 5, ...)

Debemos guardanos la profundidad asi como el vertice padre de cada vertice asignado durante la busqueda en profundidad, para luego poder reconstruir el camino.

La profundidad que alcance el vertice mas profundo sera el numero de cajas que podran meterse unas dentro de otras y el camino sera la inversa el camino de vuelta desde ese vertice susodicho.