В графе имеется N узлов (1 ≤ N ≤ 2⋅10 ^ 5) и M (1 ≤ M ≤ 2⋅10 ^ 5) направленных ребер. Каждый узел имеет присвоенный номер (целое число в диапазоне 1 ... N), который мы пытаемся определить.
Все узлы с определенным назначенным номером будут иметь направленные ребра, ведущие к другим узлам с другим определенный присвоенный номер. Это также подразумевает, что если один узел имеет несколько направленных ребер, выходящих из него, то все узлы, к которым он ведет, имеют одинаковый назначенный номер. Мы должны использовать эту информацию, чтобы определить присвоение номеров таким образом, чтобы число различных номеров среди всех узлов было максимальным.
Поскольку существует несколько возможных ответов, на выходе должно быть присвоение, которое минимизирует числа, назначенные узлам 1 ... N, в этом порядке. По сути, ответ лексикографически наименьший.
Пример:
На графике из 9 узлов и 12 ребер вот ребра. Для двух целых чисел i и j в каждой строке имеется направленное ребро от i до j.
3 4
6 9
4 2
2 9
8 3
7 1
3 5
5 8
1 2
4 6
8 7
9 4
Правильное назначение состоит в том, что узлы 1, 4, 5 имеют присвоенный номер 1; узлам 2, 6, 8 присвоен номер 2; а узлам 3, 7, 9 присвоен номер 3. Это имеет смысл, потому что узлы 1, 4, 5 ведут к узлам 2, 6, 8, которые ведут к узлам 3, 7, 9.
Чтобы решить эту проблему, я подумал, что вы можете создать граф с отключенным каждый из подграфов представляет группу узлов с одинаковым присвоенным номером. Чтобы сделать это, я мог бы просто просканировать все узлы, и если у узла есть несколько направленных ребер к другим узлам, вы должны добавить их в свой график как связанный компонент. Если некоторые из узлов уже присутствуют в графе, вы можете просто добавить ребра между текущими компонентами.
Затем для остальных узлов вы можете найти, к каким узлам они направили ребра, и каким-то образом используйте эту информацию, чтобы добавить их в свой новый график.
Будет ли эта стратегия работать? Если так, как я могу правильно реализовать вторую часть моего алгоритма?
РЕДАКТИРОВАТЬ 1: Ранее я неправильно интерпретировал формулировку задачи; Теперь я опубликовал правильную интерпретацию и мой новый подход к проблеме.
РЕДАКТИРОВАТЬ 2: Поэтому, как только я go пройду по всем узлам один раз, добавив ребра, как я описал выше, я бы определил компоненты для каждого узла. Затем я снова перебрал бы узлы, на этот раз убедившись, что рекурсивно добавляю остальные ребра в граф. Например, если узел с назначенным номером имеет направленное ребро для узла, которому не был назначен номер, я могу добавить этот узел к назначенному ему компоненту. Я также могу использовать Union Find для обслуживания компонентов.
Хотя это будет достаточно быстро, я беспокоюсь, что могут быть ошибки - например, когда я делаю это рекурсивное решение, возможно, что когда узлу назначен номер, другие узлы с присвоенными номерами, которые подключены к этому узлу, могут не работать с ним. В принципе, было бы противоречие. Я должен был бы найти решение для этого.