а про геометрические индексы и окто деревья где узнать

?)

я думаю сейчас самостоятельно написать просто такой хеш попробовать, впринципе должно быть легко

только ещё нужно мапу, придётся свой аллокатор писать т.к. это происходит очень часто в теории(пересчитывание столкновений для разных объектов)

есть же замечательные поисковики: Google, yandex

Есть много замечательного материала с картинками и подробным объяснением

А если не помогают собственно поисковики всегда есть всякие гугл сколары

Имеется n пользователей, каждому из них соответствует список email-ов (всего у всех пользователей m email-ов).
Например:
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, значит это один и тот же пользователь. Требуется построить
и реализовать линейный алгоритм, выполняющий слияние пользователей.

Как представить эту задачу в виде графа и реально ли она невыполнима?

Свисок вершин - это email-ы, ребра это связные email.
из построенного несвязанного графа можно выделить компоненту связаности которая и окажется тем слитым юзером.
Но что нам нужно найти и доказать?

А какие данные нужны на выходе? Для каждого вывести список всех принадлежащих ему почт?

да

Звучит как система непересекающихся множеств

+

она через графы решается 99%

но как представить в виде графа не пойму

Вершины - это емейлы
Для каждого пользователя соединяем емейлы между собой в цепочку
Получившиеся компоненты связности - это слитые пользователи

Ну, посмотрим на двудольный граф, в котором вершины левой доли это юзеры, а правой - емейлы.

Тогда тебе нужны компоненты связности.

Соответственно можно завести СНМ на одной из долей, например на юзерах. А потом для каждой почты смержить всех юзеров с такой почтой.

в таком графе задача уже решена - все рёбра представлены всеми связями
нет разницы между ребрами связями изначальных данных и конечных

Я имел в виду, что нужно соединять емейлы между собой для каждого изначального, ещё не слитого, пользователя. Тогда получившиеся компоненты связности образуют новых, слитых.

типо разные рёбра