@Nem0_o

Как дополнить топологическую сортировку?

Часть кода, DFS и топологическая сортировка:
void dfs (int v) {
  used[v] = true;
  for (size_t i=0; i<g[v].size(); ++i) {
    int to = g[v][i];
    if (!used[to])
      dfs (to);}
  ans.push_back (v);
}
void t_sort() {
  for (int i=0; i<n; ++i)
    used[i] = false;
  ans.clear();
  for (int i=0; i<n+1; ++i)
    if (!used[i])
    dfs(i);
}

Не получается сделать так, чтобы сортировка не происходила при наличии цикла в графе.
  • Вопрос задан
  • 2397 просмотров
Решения вопроса 1
@Mercury13
Программист на «си с крестами» и не только
С двузначными метками посещения (bool used[]) — никак.

Надо перейти на трёхзначные метки (UNVISITED, PARTLY_VISITED, VISITED).

void dfs (int v) {
  state[v] = PARTLY_VISITED;
    .....
  state[v] = VISITED;
  ans.push_back (v);
}


Неплохой пример есть в вашем предыдущем вопросе.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы