ГР
у нас будет граф из набора графов?
типо граф из n (пользователей) графов по m (email у каждого) элементов
которые мы потом пытаемся связать
Size: a a a
2021 June 27
ГР
С
Нет. Сейчас нарисую, секунду.
KV
а как в ответе должны быть представлены пользователи с пересекающимся имэйлом? "user1,user2"?
ГР
user1 -> 1@1.ru, 2@2.com
user2 -> 1@1.ru, 3@3.com
на выходе
user1 (или юзер 2) как угодно = 1@1.ru, 2@2.com, 3@3.com
user2 -> 1@1.ru, 3@3.com
на выходе
user1 (или юзер 2) как угодно = 1@1.ru, 2@2.com, 3@3.com
С
Вот адреса трёх первых пользователей из вашего примера. (для простоты будем считать, что четвертого и пятого пока нет)
ГР
да
С
1. Соединяем между собой почты первого юзера.
С
2. Теперь соединяем между собой почты второго юзера.
С
3. И третьего.
С
У нас получилось две компоненты связности. Каждая из них содержит все емейлы нового, слитого юзера. Готово.
ГР
так
ГР
да
С
Это всё, задача решена, просто выведите каждую компоненту связности :)
ГР
это ещё ничего не решает.
С
Как это? Мы же объединили пользователей в слитых, как вы хотели. Имена исходных пользователей можно восстановить через обратный индекс любого емейла в каждой компоненте.
ГР
вот у меня есть n графов по m элементов, как вывести эту компоненту связности
и какова сложность алгоритма
и какова сложность алгоритма
С
У вас на старте один граф и в конце один граф. Почитайте, что такое компоненты связности: https://brestprog.by/topics/connectivity/
И создание нашего графа, и поиск компонент связности - линейные задачи. O(n + m).
И создание нашего графа, и поиск компонент связности - линейные задачи. O(n + m).
N
Эту задачу ещё можно решить через disjoinset.