правельно сложность связности графа будет = n
но сложность решения задачи <> n

явно неверно сопоставляем задачу и граф

Геннадий, ваши заблуждения основаны на том, что для поиска компонент связности якобы в каком-то случае может потребоваться n**2 сравнений. Мне кажется, вы не понимаете алгоритм, по которому они ищутся. Я кидал статью, там доступно объяснено, как это делать.

Почему сложность решения задачи не равна n?

ну вот у вас по 1 email у n пользователей,
как вы проверите всех пользователей?
первого вы сравниваете с остальными (n-1), 2 - (n-2)... n-1 пользователя сравниваете с пользователем n

n ни сравниваете ни с кем. кол-во операций будет n(n-1)/2

Зачем сравнивать первого с остальными?

чтобы проверить совпадения

Зачем?

Если вы придумали решение за n^2 это не значит что сложность задачи n^2

ок, я её упростил по максимум по 1 email у n пользователей
по какому алгоритму сложность будет линейной?

По тому, который я вам рассказывал.

В получившемся графе просто нужно найти компоненты связности. Для этого есть линейный алгоритм. Всё, после этого ничего дополнительно проверять не нужно. Ваши компоненты связности и будут слитыми воедино юзерами.

Почитай про физ движки. Задачу столкновения физических тел делят на несколько этапов. Во первых нужно упростить сами объекты. Bounding box или bounding shperes (у тебя это уже есть). И найти сначала все пары столкновений сфера-сфера (broad-phase), потом уже вычислять более точно какие вершины или поверхности столкнулись и насколько глубоко взаимопроникновение (так как придеться еще выталкивать их из вне и вычислять возможно импульсы). Но основная задача это конечно максимально быстро найти пары сфера-сфера. Есть простой способ O(N^2), а есть более умный - напримр сначала сортировать объекты вдоль дискретных координат (сетки) для каждой оси и дальше уже линейно находить пары (Sweep/sort and Prune) O(N log N), есть Binary Space Partition (BSP) или Quad/Octa tree, можно еще через Separating Axis Theorem. В общем, там есть где разгуляться. Но линейной сложности там точно никогда не будет

По алгоритму который ищет компоненты связности в графе)

Например при использовании хэш-таблицы: делаем таблицу, в которой ключи это емейлы а значения - это список пользователей, у которых есть такой емейл.

Думаю понятно, как ее заполнить за линию.

нет не понятно как линейно заполнить

for (user, email) in input
   if not email in table:
       table[email] = []
   table[email].append(user)

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

Тогда можно просто в графе пользователей провести ребро из первого ко второму, из второго к третьему и т.д.

Получится граф линейного размера, каждая компонента связности которого - это ровно те юзеры, которых надо склеить

if not email
подразумевает перебор всех email в таблице которую пытаетесь получить.
1 email - 0  проверок.
2 email - 1 проверка
...
n-1 email - n-2 проверок
n email - n-1 проверка (перебор предыдущих n-1 емайл в таблице которую пытаетесь получить) сложность операций будет n(n-1)/2