Расставить 26 латинских слов в соответствии латинскому алфавиту из 26 букв (одно слово - одна буква)
Нам даны 26 латинских слов и соответственно латинский алфавит из 26 букв. Вывести true, если возможно расставить все слова в соответствии букве, которую оно имеет (одно слово - одна буква и должен быть затронут весь алфавит), иначе false. Например, есть слова "с", "bc" и "ab", Значит, буквам a b и с можно соответственно отнести слова "ab", "bc" и "c".
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Построить двудольный граф, одна доля которого содержит слова, вторая - алфавит, а ребра соединяют каждое слово с содержащимися в нём буквами.
Построить максимальное паросочетание (в данном случае оно должно быть совершенным, т.е. все узлы задействованы)
Подойдёт, например, алгоритм Куна или алгоритм Форда-Фалкерсона, оба работают за O(VE)