Size: a a a

2021 June 27

С

Степан in pro.algorithms
Ну да, по канону через DSU, но Геннадий попросил придумать решение именно на графах)
источник

ГР

Геннадий Романов... in pro.algorithms
вот у нас 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 операций
сложность квадратичная
источник

ГР

Геннадий Романов... in pro.algorithms
грубо говоря граф из n точек : 1, 2... n
источник

С

Степан in pro.algorithms
Что вы, компоненты связности ищутся через обыкновенный поиск в глубину (он линейный). Прямо в скинутой статье об этом написано.
источник

ГР

Геннадий Романов... in pro.algorithms
не осмыслю я как переложить задачу на графы,
вот если упростить у каждого пользователя 1 email.
то нам нужно перебрать n пользователей (сравнить с остальными)
1:  n-1 проверок
....
n-1: 1 проверка..
итого (n-1)(n-1 +1)/2 = n(n-1)/2 ну сложность квадратичная как ни крути

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

ГР

Геннадий Романов... in pro.algorithms
user 1 : 1@mail.ru
user 2 : 2@mail.ru
...
user n : n@mail.ru

мы первого сравниваем с n-1 пользователями (с user2 по user n)
и т.д.
user n-1  сравниваемся с 1 usern
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Может все таки структуру графа использовать?)
источник

ГР

Геннадий Романов... in pro.algorithms
да неправельно мы что -то используем для примера с одним 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
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Может все таки структуру графа использовать?)
источник

ГР

Геннадий Романов... in pro.algorithms
будет граф из n вершин без рёбер, поиск связных рёбер будет равен = n
явно неверное представление задачи в виде графа
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
источник

С

Степан in pro.algorithms
Евгений, ну это же не я туплю, решение графом похоже на правду?
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Ну да, просто связные компоненты двудольного графа
источник

С

Степан in pro.algorithms
Я выше кидал решение обычным графом, где все вершины - это уникальные емейлы
@Relect84, если моё решение не зашло, попробуйте ещё двудольным графом, где с одной стороны пользователи, с другой - почты

https://brestprog.by/topics/bipartite/
источник

С

Степан in pro.algorithms
Для поиска компонент связности такую кучу операций производить не нужно. Вам нужен простой поиск в глубину, он всегда линеен по времени.
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Ну это то же самое примерно)
источник

ГР

Геннадий Романов... in pro.algorithms
упростим, если у нас у n пользователей по 1 email
то будет граф с p вершин и z ребёр, причём p+z = n  
сложность поиска связности такого графа всегда будет = n
на деле сложность будет = n только если все email одинаковые. (граф из одной точки и рёбер к самому себе)
но если все email разные - каким образом алгоритм будет линейным?
источник

ГР

Геннадий Романов... in pro.algorithms
нет стоп неверное представляем.
p+z <>n
источник

ГР

Геннадий Романов... in pro.algorithms
просто будет граф из p точек  без рёбер, где p = n - число совпадений
источник

С

Степан in pro.algorithms
Если все email разные - в графе не будет ни одного ребра. Ища компоненты связности, вы пробежитесь по всем n вершинам, увидите, что ни у одной нету рёбер, и зафиксируете, что у вас n компонент связности.
источник