3. Поиск в глубину

Разбор задачи 1251. Шкатулки

В данной задаче отношения возможности вложить одну шкатулку в другую образуют ациклический ориентированный граф и можно применить поиск в глубину для максимума вложенности.

Объявление переменных.

var s:array [1..1000,1..3] of integer; { размеры шкатулок }
  imax, { номер шкатулки, в которой помещается больше всего }
  i,t,k,j,
  n:integer; { общее количество шкатулок }
  m, { максимальное количество вложенных шкатулок }
  f: array[1..1000]of integer; { номер самой внешней вложенной шкатулки }

  { ввод данных }
  read(n); 
  for i:=1 to n do 
  begin
    read(s[i,1],s[i,2],s[i,3]);
    { сортировка трех размеров в порядке возрастания }
    for j := 1 to 2 do 
      for k:=j+1 to 3 do
        if s[i,j]>s[i,k] then
        begin
          t:=s[i,j];s[i,j]:=s[i,k];s[i,k]:=t;
        end;
  end;

Поиск номера шкатулки, в которой помещается больше всего других шкатулок.

  imax:=1; { пусть лучшей является 1 шкатулка }
  for i:=1 to n do
  begin
    dfs(i); { вычисляем, сколько шкатулок может поместиться в i-ю } 
    if m[i]>m[imax] then { результат улучшился }
      imax:=i; { запоминаем новый номер лучшей шкатулки }
  end;

Поиск максимума вложенных шкатулок производится рекурсивной подпрограммой.

procedure dfs(i:integer);
var j:integer; { используемые для цикла переменные должны быть локальными }
begin
  if m[i]>0 then exit; { уже обрабатывали }
  m[i]:=1; { хотя бы сама эта шкатулка }
  for j := 1 to n do
    if (s[j,1]<s[i,1]) and (s[j,2]<s[i,2]) and (s[j,3]<s[i,3]) then
    begin { j-я шкатулка входит в i-ю }
      dfs(j); { вычисляем, сколько шкатулок может поместиться в j-ю } 
      if m[j]+1 > m[i] then { если результат улучшился }
      begin
        m[i]:=m[j]+1; { запоминаем новое максимальное количество }
        f[i]:=j; { запоминаем номер внутренней шкатулки }
      end;
    end;
end;

Вывод результата.

  writeln (m[imax]);
  rec(imax);

Для вывода набора вложенных шкатулок вместо цикла удобнее использовать рекурсивную подпрограмму.

procedure rec(i:integer);
begin
  if f[i]>0 then { есть вложенная шкатулка }
    rec(f[i]); { сначала выводим все вложенные шкатулки }
  write (' ',i); { затем номер самой шкатулки }
end;