Сделайте эти все



40 на сегодня

Для начала попробуем разобрать один из способов решения подобных . рассмотрим контрольный пример. входные данные: 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. снова удаляем её и выходящие из нее пути. в третьем вложении мы видим, что доступны сразу две вершины - 1 и 2. их можно посетить в любом порядке, т.е. решение не единственное. будем придерживаться порядка возрастания и и вычеркнем 1 с путём, а затем и 2. в чевертом вложении остается свободная вершина 4. посещаем её, вычеркиваем - граф исчез, решена. и порядок посещения совпал с контрольным решением. теперь, когда "ручное" решение понятно, можно строить алгоритм. мы использовали граф, а граф в программировании представляется парой множеств: множеством вершин и множеством путей, их соединяющих.эти множества классически представляются двумя матрицами - матрицей смежности (отображает вершины и наличие связей) и матрицей инцидентности (отображает направление связей и, возможно, длины путей). другие варианты - списки или деревья, но они требуют набора процедур для соответствующих манипуляций.в связи с относительной простотой был выбран собственный вариант отображения графа на квадратную матрицу размера (n+1)×n, где n- количество вершин (врачей). первая строка матрицы является служебной, остальные отображают граф. в пятом вложении принятая схема отображения. собственно, из этой схемы понятна основная идея реализации. создаем матрицу, расписываем её нулями, затем заносим единицы, создавая связи. решение состоит в последовательном переборе колонок до нахождения столбцов, содержащих все нули. найденный столбец "вычеркивается" (записывается 1 в нулевой строке), а его номер - это номер посещенной вершины. процесс повторяется, пока в служебной строке не будут все единицы, либо пока не будет n раз сделан проход по столбцам (от зацикливания при отсутствии решения).поскольку программа может показаться нетривиальной, в нее внесены операторы отладки, позволяющие по шагам проследить решение. как отладкой, ясно из комментариев. если отладка не нужна, достаточно из программы удалить все строки, отмеченные \\-// pascalabc.net 3.2, сборка 1417 от 28.03.2017// внимание! если программа не работает, обновите версию! begin  var n: =readinteger; // первая строка - число врачей  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-> 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-> x=1) then begin t: =1; break end;       end;   if t=0 then writeln(-1)  else writeln(res)end.пример решения с выключенной отладкой52 3 52 3 51 53 1 3 505 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