# Toposort error

## Problem Info

I’m going CSES Game Routes.

## My Work

``````#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

// #include "debugging.h"

using std::cout;
using std::endl;
using std::vector;

constexpr int MOD = 1e9 + 7;

int main() {
int level_num;
int telep_num;
std::cin >> level_num >> telep_num;
vector<vector<int>> prev_levels(level_num);
for (int t = 0; t < telep_num; t++) {
int from;
int to;
std::cin >> from >> to;
prev_levels[--to].push_back(--from);
}

vector<bool> visited(level_num);
vector<int> level_order;
for(int i = 0; i < level_num; i++){
if (visited[i]) {
continue;
}
std::stack<std::pair<bool, int>> frontier;
frontier.push({false, i});
while (!frontier.empty()){
std::pair<bool, int> curr = frontier.top();
frontier.pop();
if (curr.first) {
level_order.push_back(curr.second);
continue;
}
visited[curr.second] = true;
frontier.push({true, curr.second});
for (int n : prev_levels[curr.second]) {
if (!visited[n]) {
frontier.push({false, n});
}
}
}
}

vector<int> num_ways(level_num);
num_ways[0] = 1;
for (int l : level_order) {
for (int prev : prev_levels[l]) {
num_ways[l] = (num_ways[l] + num_ways[prev]) % MOD;
}
}
cout << num_ways.back() << endl;
}
``````

It does a topological sort first then DP’s on the number of ways to reach each possible level.
The topological sort seems to error out, even though I copied the exact structure of it here. It’s producing duplicate elements even though the graph has no cycles. Can anyone find out what’s wrong with the toposort? It seemed to work for another problem.

read the comments of the stackoverflow post; i don’t think the code is correct.

The thing is, this worked for another problem, so I still have my doubts for it being incorrect.

But if it is, could you point me to a non-recursive topological sort?

um isn’t the graph a DAG (no cycles)?

yeah didn’t i literally say that lmao

Also I did some searching: should this implementation work?

1 Like

Kahn’s algorithm is just the bfs version of toposort

I’ll take that as a yes- thanks!