Монстры и люди

Автор разбора: Даниил Орешников

Переформулируем задачу: требуется выбрать наибольшее по размеру множество A вершин в графе, чтобы между вершинами этого множества не было ребер. Действительно, это является достаточным и необходимым условием в соответствии с задачей. Скажем, что монстры — это вершины из A, люди — вершины из , а ребра — информация о том, кто кого обвинил. По условию разрешены все ситуации, кроме ситуации «монстр обвинил монстра», то есть кроме ребра из A в A.

Будем решать задачу жадным алгоритмом: пусть существует вершина, в которую не ведет ни одно ребро, в таком случае существует оптимальный ответ, в котором эта вершина является монстром. Если в каком-то ответе рассмотренная вершина v не является монстром, то рассмотрим ребро v → u: либо u — человек, тогда ответ можно увеличить, либо u — монстр, но тогда можно сделать u человеком и v монстром, и ответ не уменьшится.

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

  1. пометим обвиненную ей вершину u человеком;
  2. удалим ребро из u в обвиненную ей вершину.

В конце, когда не останется вершин со входящей степенью 0, весь граф разобьется на циклы. Очевидно, что в цикле длины k можно выбрать вершин. Все это можно реализовать с помощью dfs с дополнительным флагом.