9. Проверка топологической сортировки

Задача

Проверьте, является ли заданная перестановка вершин топологической сортировкой ориентированного ациклического графа.

Входные данные

В первой строке указаны числа $n$ и $m$ ($1 \leqslant n, m \leqslant 10^5$) — количество вершин и рёбер. В следующих $m$ строках даны пары $u_i$, $v_i$, задающие ориентированное ребро из вершины $u_i$ в вершину $v_i$. В последней строке задана перестановка из $n$ элементов.

Выходные данные

Выведите YES, если перестановка является топологической сортировкой данного графа, и NO иначе.

Примеры

стандартный ввод      стандартный вывод
3 3                    NO
2 3
1 3
1 2
2 1 3

3 3                    YES
3 2
1 2
3 1
3 1 2

Ограничения

  • Время: 1 секунда
  • Память: 256 мегабайт
Редакционный разбор Построим массив `pos`, где `pos[v]` — позиция вершины $v$ в предложенной перестановке. Чтобы перестановка была топологической, для каждого ребра $(u, v)$ должно выполняться `pos[u] < pos[v]`. Проверяем все рёбра и при первом нарушении отвечаем «NO». Если ни одного нарушения нет, ответ «YES». Сложность $O(n + m)$: формирование `pos` и единственный проход по рёбрам.

Mentioned by