Унікальне топологічне сортування (Розбір)

Використаємо алгоритм Кана. Нагадаємо, що він підтримує чергу вершин із нульовою напівстепінню заходу – саме тих вершин, які можна поставити на наступну позицію в топологічному сортуванні. На кожній ітерації з черги видаляється вершина та додається до відповіді, а напівстепені заходу всіх її сусідів зменшуються на $1$. Вершини, напівстепінь заходу яких стає нульовою, додаються до черги.

Ключове спостереження: топологічне сортування єдине тоді й лише тоді, коли перед кожним видаленням у черзі міститься рівно одна вершина.

Складність. Кожна вершина та кожне ребро обробляються один раз, тому час роботи становить O(n + m).

Приклад

Графи з тестових прикладів виглядають так:

У першому прикладі топологічне сортування єдине:

• $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");