• Как найти повторяющиеся элементы в разных коллекциях за линейное время?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это задача на поиск компонент связности в графе. У вас двудольный граф, но это не важно. Вершины - емейлы и пользователи, ребра - соответствие пользователя емейлу. Решается обходом в глубину или обходом в ширину. Оба решения - линейные от количества ребер (в вашем случае - общее количество емейлов).

    Перенумеруйте все емейлы и всех пользователей.
    Код будет проще, если емейлы и пользователи хранятся в одном и том же пространстве номеров.
    Это реализуется с одним hashMap, который будет давать номер по строке, и одним массивом строк, который будет хранить изначальную строку по номеру. Вам еще понадобится булевый массив, чтобы хранить, является ли данная вершина пользователем или мейлом. При вводе получаете какую-то строку, и вызываете от нее функцию GetID(s, is_user), которая проверяет, есть ли данная строка в мапе. Если есть, возвращает номер. Если нет - дописывает строку в массив строк, записывает ее индекс в мап и возвращает его.

    При вводе - постройте граф.
    Храните ребра в списке смежности - массив массивов или списков, где для каждого номера-вершины вы построите список всех с ней связанных.
    При вводе у вас есть номер вершины-пользователя и вы читаете емейлы и переводите их номера. При этом добавляйте номер-емейл в список для пользователя и наоборот.

    Заведите массив пометок "обойденности" для всех вершин. Он будет int. 0 - непосещенные вершины, иначе номер компоненты связности.
    Запустите на этом графе DFS/BFS от каждой пока не обойденной вершины в цикле и помечайте все достижимые вершины новым числом (можно передавать вторым параметром в DFS). Можно сразу же во время обхода заполнять структуру ответ - один номер для пользователя и список для емейлов. Или можно после цикла с DFS завести массив списков для ответа, пройтись по массиву и распихать номера вершин по спискам. Используйте булевый массив, чтобы понять какая вершина пользователь, а какая - мейл. Из пользователей возьмите только одного предстваителя, а все емейлы запихайте в список в ответ. Потом выводите, преобразуя номера в строки с помощью имеющегося массива.
    Ответ написан
    1 комментарий