Объединение объектов в группы по общему признаку
Я не могу придумать эффективный алгоритм решения задачи. Нужно распределить программистов на группы "по интересам" по правилу: если хотя бы у одного из участников группы есть общий технологический интерес с разработчиком вне группы, тот этот разработчик входит в группу. Нужно найти минимальное количество групп, на которые можно разбить программистов.
Пример ввода
8
Python Keras Java
Swift
Kotlin Java
jQuery React
Swift Python Objective-C
React PHP
C++ Go
C# Go
Пример вывода
3
Я решил задачу крайне неэффективно, перебирая список много раз. Хотелось бы узнать другие менее затратные способы решения.
Ответы (1 шт):
Автор решения: EzikBro
→ Ссылка
Решение за O(N*logN), где N - суммарное количество интересов всех разработчиков:
1. Положим все интересы в set.
А для большей производительности лучше вообще сожмем через map<string, int>.
2. Далее строим DSU на интересах-вершинах.
3. Проходим по всем разработчикам, и если у данного больше одного интереса, то выполняем операцию DSU.union_sets(this_interests[0], this_interests[i]) для каждого i от 1 до конца.
4. Теперь в DSU есть некоторое количество групп интересов. Оно и будет являться ответом.
5. Если вам нужно узнать, какие конкретные разработчики находятся в каждой группе, то группу данного разработчика можно получить как DSU.find_set(all_interests[developer][0])
DSU - система непересекающихся множеств. Почитать о ней можно, к примеру, тут: http://e-maxx.ru/algo/dsu