Цепочки синонимов

Средняя

Две фразы заданы списками слов first и second. Есть словарь синонимов synonyms: каждая пара [x, y] означает, что x и y — синонимы. Синонимия работает в обе стороны и передаётся по цепочке: если a — синоним b, а b — синоним c, то a и c тоже синонимы. Любое слово — синоним самому себе. Фразы **совпадают по смыслу**, если в них одинаковое число слов и для каждой позиции i слова first[i] и second[i] — синонимы. Верните True, если это так, иначе False.

Пример 1

first=["a", "quick", "trip"], second=["a", "rapid", "journey"], synonyms=[["quick", "fast"], ["rapid", "fast"], ["trip", "journey"]] → True

«a» совпадает само с собой, quick → fast → rapid связаны цепочкой, trip и journey — синонимы напрямую.

Пример 2

first=["big", "house"], second=["large", "home"], synonyms=[["big", "large"], ["home", "flat"]] → False

house не связан с home ни одной цепочкой синонимов.

Пример 3

first=["hi"], second=["hi", "there"], synonyms=[] → False

Разное число слов — фразы не совпадают по смыслу.

Ограничения

1 ≤ len(first), len(second) ≤ 10⁴
0 ≤ len(synonyms) ≤ 2·10⁴, каждая пара состоит из двух слов
Все слова длиной от 1 до 20 символов и состоят из латинских букв (заглавных и строчных; регистр важен)

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Breadth-First Search Union Find Array Hash Table String

Вход

first=["a", "quick", "trip"], second=["a", "rapid", "journey"], synonyms=[["quick", "fast"], ["rapid", "fast"], ["trip", "journey"]]

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 111 тестов на сервере, включая скрытые.