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);

}