Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if:
j.x > k.x and j.y > k.y and j.z > k.z. Rotation is not allowed.
Searching some approaches on the net, I found this can be a way:
organize boxes in a directed unweighted graph where the edge (j,k) means j holds k use topological sort on the grapgh find the longest path and print it
I'm trying to better understand what will happen after doing the topological sort on the graph. If I understand correctly, I should be able to perform topological sort with a DFS-visit variation. In an example I've seen, the output of the sort is a single linked list. So if i output the list, why this is not already the longest path (meaning the longest sequence of boxes that can fit one into another)? If that's not the case and I also need to find the longest path, do I need to do it on the new graph made by the edges in the list returned by the topological sort (meaning it'll be a directed acyclic graph)?