Предположим, у меня есть список, который определяет, имеет ли пользователь (AG) доступ администратора к сайту (1-6):
A: [1,2,3]
B: [2,3,4]
C: [3,4,5]
D: [4,5,6]
E: [1,2]
F: [3,4]
G: [5,6]
Я хотел бы получить некоторые данные с каждого сайта, используяминимальное количество различных учетных данных пользователя.В приведенном выше примере решением было бы использование пользователей A и C.
Я думал о моделировании проблемы для графиков, поэтому список сайтов пользователей будет лесом, где каждый сайт является листом.
Я думал о добавлении рута, который подключается ко всем пользовательским узлам и запускает BFS, но это не дает оптимального решения.Я также думал об использовании union find, и, похоже, он работает в некоторых примерах, которые я запускал, однако я не уверен в правильности своего решения.
Я также рассмотрел использование max-поток для этой проблемы, но это, кажется, не правильное направление.
Я также не думаю, что жадный алгоритм решил бы это: (
Ужасная визуализация:
