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

Question

[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);
}

Не получается сделать так, чтобы сортировка не происходила при наличии цикла в графе.

Answer 1

[Mercury13]

С двузначными метками посещения (bool used[]) — никак.

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

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

Неплохой пример есть в вашем предыдущем вопросе.