10648. Мстители

 

Нурлашко, Нурбакыт и Жора – члены последнего клана ниндзя, сражающегося против злого правления императора Рена. После сокрушительного поражения в открытом бою они решили разделить свою армию на три лагеря и начать партизанскую войну.

Нелепые реформы одного императора Рэна позволяют проезжать дороги между городами только в одном направлении. Также он выбрал разрешенные направления дорог таким образом, чтобы невозможно было начать движение и вернуться в один и тот же город после прохождения нескольких дорог.

Прямо сейчас клан решает, где разместить свои лагеря. Армия императора Рэна совершает регулярные набеги, осматривая какой-то путь. Если армия сокрушит все три лагеря во время рейда, клан не сможет перегруппироваться и проиграет войну. Помогите клану выбрать три города таким образом, чтобы не было пути, проходящего через все три города.

 

Вход. Первая строка содержит два числа n, m (1 ≤ n, m ≤ 106) – количество городов и дорог в империи. Следующие m строк содержат пары чисел vi, ui (1 ≤ vi, ui ≤ n), описывающие направленную дорогу от vi к ui.

 

Выход. Выведите три числа – индексы городов, в которых клан должен разместить свои лагеря. Если нет таких трех городов, то выведите -1. Если существует несколько ответов, то выведите любой из них.

 

Пример входа 1

Пример выхода 1

3 2

1 2

2 3

-1

 

 

Пример входа 2

Пример выхода 2

3 2

1 2

1 3

2 3 1

 

 

РЕШЕНИЕ

графы – топологическая сортировка

 

Анализ алгоритма

В графе требуется найти три любые вершины, не лежащие на одном пути.

Запустим алгоритм топологической сортировки Кана. Найдем две вершины, которые будут одновременно находиться в очереди. В этом случае не существует пути, на котором лежат эти две вершины. Добавив к ним любую третью вершину, получим ответ.

Если при реализации алгоритма Кана очередь всегда содержит не более одной вершины, то все вершины графа лежат на одном пути.

 

Пример

Графы из тестовых примеров имеют вид:

В первом примере все три вершины лежат на одном пути. Во втором примере три вершины не лежат на одном пути.

 

Реализация алгоритма

Объявим структуры данных. Входной граф содержится в списке смежности g. Входящие степени вершин храним в массиве InDegree. 

 

vector<vector<int> > g;

vector<int> InDegree;

deque<int> q;

 

Читаем входные данные.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

InDegree.resize(n + 1);

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

 

Для каждого ребра (a, b) увеличим InDegree[b] на 1.

 

  InDegree[b]++;

}

 

Все вершины, входящие степени которых равны нулю, заносим в очередь q.

 

for (i = 1; i < InDegree.size(); i++)

  if (InDegree[i] == 0) q.push_back(i);

 

Искомые три вершины сохраним в x, y, z.

 

x = y = -1;

 

Продолжаем работу алгоритма, пока очередь q не пуста.

 

while (!q.empty())

{

 

Если очередь содержит более одной вершины, то ответ найден.

 

  if (q.size() > 1)

  {

    x = q[0];

    y = q[1];

    break;

  }

 

Извлекаем вершину v из очереди (она будет текущей в топологическом порядке).

 

  v = q.front(); q.pop_front();

 

Удаляем из графа ребра (v, to). Для каждого такого ребра уменьшаем входящую степень вершины to. Если степень вершины to станет нулевой, то заносим ее в очередь.

 

  for (int to : g[v])

  {

    InDegree[to]--;

    if (InDegree[to] == 0) q.push_back(to);

  }

}

 

Алгоритм Кана завершен. Если значение x все еще равно -1, то решения не существует.

 

if (x == -1)

  printf("-1\n");

else

{

 

Решение существует. В качестве z выбираем минимальную вершину, не равную x и y.

 

  z = 1;

  while (z == x || z == y) z++;

    printf("%d %d %d\n", x, y, z);

}