Я пытаюсь решить проблему на основе TopSort. Поскольку будет несколько действительных отсортированных топологических порядков, мне нужно вывести тот, который лексикографически наименьший, то есть сначала наименьшая доступная вершина.
Я объясню метод, который я принял, а затем опубликую код. Я сохранил массив, который содержит количество ребер для каждого узла графа. Матрица смежности также присутствует. У меня есть логический массив «посещенные», в котором хранится количество посещенных узлов, и очередь с минимальным приоритетом, чтобы выдвинуть наименьшую доступную вершину в данный момент. Вот мой код:
void dfs(int u){
visited[u] = true;
cout<<u<<" ";
list<int>::iterator i;
for(i = adj[u].begin(); i != adj[u].end(); ++i){
if(!visited[*i]){
inedge[*i]--;
if(!inedge[*i]){
pq.push(*i);
}
if(!pq.empty()){
int temp = pq.top();
pq.pop();
dfs(temp);
}
}
}
}
Теперь при первом вызове этой функции очередь с приоритетами содержит только те узлы, для которых inedge [i] = 0 (количество внутренних ребер равно нулю). Я выскакиваю минимальный узел из этой очереди приоритетов u = pq.top()
и позвоните dfs(u)
,
Но мой код дает неправильные результаты. Кто-нибудь может мне помочь, если логика, которую я здесь использовал, неверна?
Мой вход состоит из N неполных последовательностей (с пропущенными числами в каждом из N).
Входные данные:
2
1 3
2 3 4
Выход:
1 2 3 4
Это правильный ожидаемый результат, и мой код генерирует это. Но для ввода данных в этот образ
Входные данные:
6
7 8 9
7 11 9
5 11 2
3 8 9
11 10
3 10
ожидаемый результат:
3 5 7 8 11 2 9 10
Мой код выводит:
3 5 7 8 11 9 2 10
Мой код выводит неверные результаты и для нескольких других тестовых случаев, но я не знаю, как решить эту проблему.
Кажется, проблема в том, что pq.top
вызывается до того, как все исходящие ребра текущего узла будут проверены.
Рассмотрим следующий график: узлы: A, B, C; Края A-> B, A-C. Пусть C имеет меньшее значение приоритета, то есть оно должно стоять первым. Во время dfs (A) вы проверяете B перед C. Поскольку он сразу же снова берется из очереди, B обрабатывается первым (но не должно быть). Итак, вставьте все соседние узлы, прежде чем снова запрашивать очередь.