10652. Уникальная топологическая сортировка

 

Задан ориентированный невзвешенный граф. Определите, существует ли у него единственная топологическая сортировка.

 

Вход. В первой строке содержатся количество вершин n (1 ≤ n ≤ 2 * 105) и количество рёбер m (1 ≤ m ≤ 105) в графе. В следующих m строках задаются рёбра графа, каждое из которых представлено парой чисел – номерами начальной и конечной вершины.

 

Выход. Выведите “YES”, если существует единственная топологическая сортировка вершин графа, и “NO” если существует несколько вариантов сортировки. Если топологическая сортировка невозможна, выведите -1.

 

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

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

3 2

1 2

2 3

YES

 

 

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

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

3 2

1 2

1 3

NO

 

 

РЕШЕНИЕ

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

 

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

Запустим алгоритм Кана (Kahn). Если на каждой итерации алгоритма очередь всегда содержит в точности одну вершину, то топологическая сортировка уникальна.

 

Пример

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

В первом примере топологическая сортировка уникальна:

·        1, 2, 3.

Во втором примере имеются две топологические сортировки:

·        1, 2, 3;

·        1, 3, 2;

 

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

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

 

vector<vector<int> > g;

vector<int> InDegree;

deque<int> q;

 

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

 

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

  InDegree[b]++;

}

 

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

 

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

  if (!InDegree[i]) q.push_back(i);

 

Установим flag = 1, если топологическая сортировка уникальна.

 

flag = 1;

 

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

 

while (!q.empty())

{

 

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

 

  if (q.size() > 1) flag = 0;

 

Извлекаем из очереди текущую вершину v.

 

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

 

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

 

  for (int to : g[v])

  {

    InDegree[to]--;

    if (!InDegree[to]) q.push_back(to);

  }

}

 

В зависимости от значения flag выводим ответ.

 

if (flag == 1)

  printf("YES\n");

else

  printf("NO\n");