Условие: Дерево из N вершин можно представить следующим образом: сначала все вершины нумеруются числами от 1 до N. Затем выкидывается лист с наименьшим номером и выписывается номер его предка. Такая операция повторяется до тех пор, пока не останется одна вершина. Врезультате получается последовательность из (n-1) числа. Требуется написать программу, которая по последовательности восстанавливает само дерево.
Технические условия: Входной файл: INPUT.TXT Выходной файл: OUTPUT.TXT Ограничение по времени: 2 секунды на тест.
Входные данные: Во входном файле на первой строке (N-1) (2<=N<=7500) число.
Выходные данные: Выходной файл должен содержать N строк. В i-й строке должен быть список вершин, с которыми соеденина i-я вершина в порядке возрастания.
---------- cut ---------- Идея решения. Анализируя алгоритм получения данной последовательности по дереву, нетрудно понять, что количество раз, которое номер вершины встречается в последовательности равняется степени вершины, уменьшенной на 1, то есть количеству потомков этой вершины. Зная степени вершин, нетрудно составить список всех листьев, и выбрав из них наименьший(то есть имеющий наименьший номер), можно установить к какой вершине он был подвешен. Далее эмулируем удаление этого листа, то есть уменьшеем степень его предка на 1, если предок становится листом, добавляем его в очередь рассматриваемых листов. Всего эту операцию необходимо и достаточно повторить (n-1) раз, чтобы для каждой вершины (кроме имеющей максимальный номер) определить, к какой вершине она была подвешена.
В нашем случае важно быстро находить лист с наименьшим номером (см. ограничение по времени), поэтому имеет смысл построить приоритетную очередь для листьев. Вывод ответа тоже оптимизирован, чтобы хватило времени. ---------- cut ----------
var list : array[1..7500] of integer; {Здесь храним исходную последовательность} m : array[1..7500] of integer; {Степени вершин, уменьшенные на 1} tree : array[1..7500] of integer; {Номера предков для всех вершин} heap : array[0..7500] of integer; {Приоритетная очередь для листьев} n, i, j : integer; v : integer; written : boolean;
procedure add(x : integer); {Процедура добавления элемента в очередь} var i, d : integer; begin inc(heap[0]); i := heap[0]; d := i div 2; while (d > 0) and (heap[d] > x) do begin heap[i] := heap[d]; i := d; d := i div 2; end; heap[i] := x; end;
function min(i, j : integer) : integer; {Функция, возвращающая номер минимального элемента из i-го и j-го, j>i!} begin if (j > heap[0]) or (heap[i] < heap[j]) then min := i else min := j; end;
function getfirst : integer; {Функция, возвращающая первый элемент очереди, и удалающая его из очереди} var i, d : integer; x : integer; begin getfirst := heap[1]; x := heap[heap[0]]; dec(heap[0]); i := 1; d := min(2, 3); while (d <= heap[0]) and (heap[d] < x) do begin heap[i] := heap[d]; i := d; d := min(i*2, i*2+1); end; heap[i] := x; end;
begin assign(input, 'input.txt'); reset(input); while not seekeof do begin inc(n); read(list[n]); inc(m[list[n]]); end; inc(n); close(input); for i := 1 to n do if m[i] = 0 then add(i); for i := 1 to (n-1) do begin tree[getfirst] := list[i]; {Записать номер предка} dec(m[list[i]]); {Уменьшить степень предка} if m[list[i]] = 0 then add(list[i]); {Если получили лист, добавить его в очередь} end; for i := 1 to (n-1) do inc(m[list[i]]); {Опять считаем степени вершин, это нам понадобится для оптимизации вывода ответа} assign(output, 'output.txt'); rewrite(output); for i := 1 to n do begin v := tree[i]; if (v > 0) then written := false else written := true; j := 0; while m[i] > 0 do begin inc(j); if tree[j] = i then begin if (v < j) and (not written) then begin write(v, ' '); written := true; end; write(j, ' '); dec(m[i]); end; end; if not written then write(v); writeln; end;close(output);end.
