Автор задачи: Александр Гордеев, разработчик: Егор Юлин
Для удобства заменим слова на номер их следования во вводе (для этого просто пользуемся unordered_map. После этого построим ориентированный граф. У нас есть вершины (слова) и ребра между ними (замены).
Рассмотрим очевидные случаи, когда мы не можем уменьшить количество слов:
Введем более сильное утверждение: мы не сможем уменьшить количество слов, если все слова уже находятся в разных компонентах сильной связности, при этом ни одна не является предком любой другой. Действительно, в таком случае, очевидно, актуальных замен не осталось, а в противном случае — есть путь в графе, вдоль которого можно сделать замену.
Тогда будем действовать следующим образом: найдем все компоненты сильной связности, из которых не исходит ребер (стоки) — их количество и является ответом. Как мы показали выше, из ситуации, в которой в каждой из этих компонент осталось по одному слову, количество слов уменьшить не получится. Более того, это точная нижняя оценка на ответ, так как минимум по одному слову из каждой из этих компонент останется — их нельзя заменить ни на какое слово из других компонент. Получаем решение с временем работы $$$\mathcal{O}(n + m)$$$.