Я предполагаю, что вы ищете ориентацию ребер, так что
- общий граф представляет собой DAG, а
- исходные узлы DAG - это те, которые вы указали.
А пока давайте проигнорируем второе ограничение. Простой способ сделать весь граф DAG состоял бы в том, чтобы назначить порядок 1 ... n узлам, тогда ребра всегда будут указывать от более низких узлов к более высоким узлам. Поэтому вопрос заключается в том, как присвоить числа таким образом, чтобы получить второе свойство.
Я полагаю, что вы можете сделать это, запустив BFS над графиком, заполнив очередь всеми k ваших root узлов. Если вы пронумеруете узлы в порядке их обнаружения, вы получите DAG (любой порядок узлов дает DAG). Кроме того, предполагая, что нет двух корней, смежных друг с другом, и что в каждом связанном компоненте графа есть по крайней мере один root, ваши корни будут единственными корнями.
Чтобы увидеть это, предположим, что нет ваши корни смежны и граф связан, а затем предположим, что какой-то другой узел является root. Возьмите узел с наименьшим номером, кроме одного из выбранных вами узлов, который также равен root. Поскольку узлу был присвоен номер, он должен быть обнаружен в BFS, поэтому он находится рядом с другим узлом с меньшим номером, который также был найден в BFS. Но тогда ребро от узла с более низким номером будет иметь стрелку в узле с более высоким номером, поэтому это не будет root.
(Если у вас есть два соседних узла, которые хотят чтобы быть корнями, нет способа заставить это работать, так как у одного будет стрелка в другом.)
В целом, это выполняется за время O (m + n), потому что это просто BFS над графиком.