вот у нас n юзеров по 1 различному email (m=1) чтобы проверить связность всех вершин нужно операций 1 вершина : n-1 операции 2 вершина: n-2 операции ... n-1 вершина : 1 операция n вершина : 0 операций итого: n-1(n-1 + 1) /2 = n(n-1)/2 операций сложность квадратичная
не осмыслю я как переложить задачу на графы, вот если упростить у каждого пользователя 1 email. то нам нужно перебрать n пользователей (сравнить с остальными) 1: n-1 проверок .... n-1: 1 проверка.. итого (n-1)(n-1 +1)/2 = n(n-1)/2 ну сложность квадратичная как ни крути
да неправельно мы что -то используем для примера с одним email в худшем случае user 1 : 1@mail.ru user 2 : 2@mail.ru ... user n : n@mail.ru
мы 1-го сравниваем с n-1 пользователями (с user2 по user n) 2-го сравниваем с n-2 пользователей (с user3 по user n) и т.д. user n-1 сравниваемся с 1 user n user n не сравниваем ни с кем кол-во операций n-1 + n-2 + ...1 = (n-1 + 1) (n-1)/2
Я выше кидал решение обычным графом, где все вершины - это уникальные емейлы @Relect84, если моё решение не зашло, попробуйте ещё двудольным графом, где с одной стороны пользователи, с другой - почты
упростим, если у нас у n пользователей по 1 email то будет граф с p вершин и z ребёр, причём p+z = n сложность поиска связности такого графа всегда будет = n на деле сложность будет = n только если все email одинаковые. (граф из одной точки и рёбер к самому себе) но если все email разные - каким образом алгоритм будет линейным?
Если все email разные - в графе не будет ни одного ребра. Ища компоненты связности, вы пробежитесь по всем n вершинам, увидите, что ни у одной нету рёбер, и зафиксируете, что у вас n компонент связности.