Почему это работает
- Элементы Union-Find — аккаунты. owner хранит первый аккаунт каждого email, поэтому повторный email связывает аккаунт с тем первым, а связи не рвутся.
- Связь переходит дальше: аккаунт 2 встречает аккаунт 1, который уже под аккаунтом 0, и все трое оказываются под одним корнем, хотя аккаунт 2 с аккаунтом 0 не встречался.
- Группировка по корню аккаунта собирает все email человека в одном месте; множество убирает повторы, а из аккаунта берём только имя.
Сложность
Время O(E · h + E log E) для E email всего: до двух find на email глубиной с дерево (здесь до числа аккаунтов, почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее), плюс сортировка. Память O(E) на owner и groups.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗