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.