Смотровые площадки Ала-Арчи


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В ущелье Ала-Арча оборудовали n смотровых площадок и m спусков между ними. Спуск i ведёт с площадки a[i] на площадку b[i], и подняться по нему обратно нельзя; так как каждый спуск ведёт вниз, по спускам невозможно вернуться на уже пройденную площадку.

Турклуб «Тенгри» хочет отправить несколько групп. Каждая группа начинает на любой площадке и идёт только по спускам, пока не решит остановиться. Нужно, чтобы каждая площадка была посещена хотя бы одной группой (группы могут проходить одни и те же площадки и спуски). Какое наименьшее число групп понадобится?

Рисунок

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

В первой строке — два целых числа n и m (1 ≤ n ≤ 1500, 0 ≤ m ≤ 10⁵). В каждой из следующих m строк — два различных числа a[i], b[i] (1 ≤ a[i], b[i] ≤ n). Гарантируется, что циклов нет.

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

Выведите наименьшее количество групп.

Пример 1

Вход:

6 6
1 2
2 4
3 4
4 5
4 6
1 3

Выход:

2

Пояснение

На рисунке — площадки примера. Хватит двух групп: 1 → 2 → 4 → 5 и 3 → 4 → 6. Площадка 4 посещается обеими группами — так можно. Одной группы не хватит: площадки 5 и 6 нельзя посетить одной группой.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 15.

Подсказка

Теорема Дилуорса: наименьшее число цепей, покрывающих частично упорядоченное множество, равно наибольшему размеру антицепи.


Комментарии

Еще нет ни одного комментария.