Задача с собеседования в Яндекс

Имеется n пользователей, каждому из них соответствует список e-mail-ов (всего m). Например:

user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net

Считается, что если у двух пользователей общий email, значит, это один и тот же пользователь.

Требуется реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их e-mail-ами (такой же как на входе). В качестве имени можно брать любое из исходных имен. Список e-mail-ов должен содержать уникальные e-mail-ы. Параметры n и m произвольные.

В указанном примере ответ будет такой
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com

Нужно решение с линейной асимптотикой

Решение:
Довольно стандартная задача
Построим граф на пользователях такой, что два пользователя лежат в одной компоненте связности тогда и только тогда, когда они должны быть объединены в одного пользователя. Для этого используем хеш-мапу: для каждого e-mail-а список пользователей.
Соединим последовательно цепочкой этих пользователей друг с другом в графе. Граф будет иметь размер порядка O(n + m). После этого найдем в графе компоненты связности и восстановим по ним ответ на задачу

Итоговая асимптотика O(n + m)

@algoses