Максу нужно пройти медкомиссию, состоящую из N различных врачей.Теснее у стойки

Примерывходные данные52 3 4001 51 2выходные данные2 3 5 4 1 входные данные52 3 52 3 51 53 1 3 50выходные данные5 3 1 2 4

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

Ответа не существует, если в графе есть цикл

Для начала попробуем разобрать один из способов решения сходственных задач.

Осмотрим контрольный пример.
Входные данные:
5 - это количество врачей, т.е. нижеследующих строчек.
2 3 5 - 1-й врач. У него 2 предшественника - врачи 3 и 5
2 3 5 - 2-й доктор. У него 2 предшественника - лекари 3 и 5
1 5 - 3-й врач. У него 1 предшественник - доктор 5
3 1 3 5 - 4-й доктор. У него 3 предшественника - лекари 1, 3 и 5
0 - 5-й доктор. У него нет предшественников.
Вариант результата: 5 3 1 2 4 - в таком порядке посещаются лекари.

Изобразим эти данные графически. В кружочках проставим номера лекарей и соединим кружочки стрелками, отображающими взаимосвязи (первое вложение). Приобретенный набросок - ни что другое, как направленный граф.

Решение будет состоять в поиске порядка посещения всех вершин графа ("лекарей") в согласовании с доступными маршрутами ("очередностью").
Явно, что первой нужно посетить верхушку, из которой пути только выходят. Если ни одной таковой верхушки нет - задача решения не имеет. В нашем случае такая верхушка есть - номер 5 и она помечена зеленоватым. После посещения мы устраняем эту вершину и все водящие из нее пути. Получаем картину, представленную вторым вложением. Повторяем наше рассуждение и обретаем вершину 3. Опять удаляем её и выходящие из нее пути. В 3-ем вложении мы видим, что доступны сходу две верхушки - 1 и 2. Их можно посетить в любом порядке, т.е. решение не единственное. Будем придерживаться порядка возрастания и и вычеркнем 1 с маршрутом, а потом и 2. В чевертом вложении остается свободная вершина 4. Навещаем её, вычеркиваем - граф пропал, задача решена. И порядок посещения совпал с контрольным решением.

Сейчас, когда "ручное" решение понятно, можно строить алгоритм.
Мы использовали граф, а граф в программировании представляется парой множеств: обильем вершин и множеством путей, их соединяющих.
Эти огромного количества классически представляются 2-мя матрицами - матрицей смежности (показывает верхушки и наличие связей) и матрицей инцидентности (показывает направление связей и, вероятно, длины путей). Иные варианты - списки либо деревья, но они требуют комплекта процедур для подходящих манипуляций.

В связи с относительной простотой задачки был избран свой вариант отображения графа на квадратную матрицу размера (n+1)n, где n- количество вершин (лекарей). 1-ая строчка матрицы является служебной, другие показывают граф. В 5-ом вложении приведена принятая схема отображения. Фактически, из этой схемы понятна главная идея реализации. Создаем матрицу, расписываем её нулями, потом заносим единицы, творя связи. Решение состоит в поочередном переборе колонок до нахождения столбцов, содержащих все нули. Найденный столбец "вычеркивается" (записывается 1 в нулевой строке), а его номер - это номер посещенной вершины. Процесс повторяется, пока в служебной строке не будут все единицы, или пока не будет n раз изготовлен проход по столбцам (от зацикливания при отсутствии решения).

Поскольку программка может показаться нетривиальной, в нее внесены операторы отладки, дозволяющие по шагам проследить решение. Как управлять отладкой, светло из комментариев. Если отладка не нужна, довольно из программы удалить все строчки, отмеченные \\-

// PascalABC.NET 3.2, сборка 1417 от 28.03.2017
// Внимание! Если программа не работает, обновите версию!

begin
  var n:=ReadInteger; // 1-ая строчка - число лекарей
  var a:=MatrFill(n+1,n,0); // матрица посещений
  var t:integer;
  for var i:=1 to n do begin // цикл ввода по каждому врачу
    var k:=ReadInteger; // количество врачей-предшественников
    for var j:=1 to k do begin
      Read(t);
      a[t,i-1]:=1
      end;
    end;
  t:=0;
  var res:='';
  var debug:=true; //- debug:=false перекрывает отладочную выдачу
  if debug then begin //-
    Writeln('начальная матрица'); //-
    a.Println(2); Writeln //-
    end; //-
  for var m:=1 to n do begin
    for var j:=1 to n do begin
      var c:=a.Col(j-1);
      if c[0]=0 then begin
        if c.All(x-gt;x=0) then begin
          Res+=j+' ';
          if debug then Writeln(Res); //-
          a[0,j-1]:=1;
          for var i:=0 to n-1 do a[j,i]:=0;
          if debug then begin //-
            a.Println(2); Writeln //-
            end //-
          end
        end;
      end;
    if a.Row(0).All(x-gt;x=1) then begin t:=1; break end;
    end;
  if t=0 then Writeln(-1)
  else Writeln(Res)
end.

Пример решения с выключенной отладкой
5
2 3 5
2 3 5
1 5
3 1 3 5
0
5 3 1 2 4

Пример со включенной отладкой (можно начальные данные для удобства все писать в одной строке)
5 2 3 5 2 3 5 1 5 3 1 3 5 0
начальная матрица
 0 0 0 0 0
 0 0 0 1 0
 0 0 0 0 0
 1 1 0 1 0
 0 0 0 0 0
 1 1 1 1 0

5
 0 0 0 0 1
 0 0 0 1 0
 0 0 0 0 0
 1 1 0 1 0
 0 0 0 0 0
 0 0 0 0 0

5 3
 0 0 1 0 1
 0 0 0 1 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0

5 3 1
 1 0 1 0 1
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0

5 3 1 2
 1 1 1 0 1
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0

5 3 1 2 4
 1 1 1 1 1
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0

5 3 1 2 4