Почему это работает
- Равенство заразно: a == b и b == c дают a == c. Поэтому буквы, связанные равенствами, образуют группы, и все буквы группы получают одно значение.
- Разным группам всегда можно дать разные значения, поэтому уравнения выполнимы ровно тогда, когда ни у одного неравенства обе буквы не в одной группе, — это сравнение корней.
- Неравенство можно проверять, только когда учтены все равенства: следующее равенство ещё может свести его буквы в одну группу, как "b==c" здесь.
Сложность
Время O(m · h) для m уравнений: два прохода и два find на уравнение, а дерево из не более чем 26 букв высотой не больше 26, так что это O(m). Память O(1): в parent по ячейке на букву алфавита.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗