Альтернативное задание. Только для группы 394.
Консольное приложение, на вход принимает имя входного и выходного файлов:
java ExternalTreeDepth <in_filename> <out_filename>
На входе файл с деревом заданным списком рёбер. Все вершины пронумерованы от 1 до n. Каждая строчка имеет формат: вершина<пробел>дочерняя вершина. Листья имеют вид <номер вершины><пробел>0. Например:
1 5
3 2
5 0
4 1
4 3
На выходе должен быть файл, в котором записана максимальная глубина дерева (по количеству вершин в самом длинном пути):
3
Ограничения: программа должна работать с памятью -Xmx64M и уметь сортировать файлы до 1Гб. Должна делать O(nlogn) операций ввода/вывода во внешнюю память.
Теория тут: https://algo2.iti.kit.edu/download/mem_hierarchy_06.pdf