These are the notes for Competitive Programming episode 49, the fifth episode of the graphs section. Until now every road could be used in both directions; today every edge has a direction. Festival Kitchen asks for the smallest cooking order that obeys rules like "cook a before b": trying every order with next_permutation is correct but Time Limit Exceeded at only 13 dishes (13! ≈ 6.2 · 10^9 orders). A cook's prep board that counts how many dishes each dish still waits for is Kahn's algorithm: in-degrees plus a queue of ready dishes, O(n + m). A plain queue prints the valid but not smallest order 3 4 1 5 2; a min-heap prints 3 1 4 5 2. Forgetting to check that every dish was placed prints 1 4 where the answer is IMPOSSIBLE. Wedding Prep needs the minimum finishing time with unlimited helpers, which is the longest path in a DAG: plain recursion is TLE on a 60-layer graph (2^60 calls), DP in index order prints 10 where 11 is right, and DP in topological order is accepted. One-way Roads counts routes from town 1 to town n: without the modulo the count overflows to -2984622845537545263; with % MOD at every addition it prints 886041711. Three stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
The head cook of a festival kitchen has a prep board. Next to every dish she writes a tally: how many other dishes it is still waiting for (the dal needs the tempering, the biryani needs the fried onions). Every dish whose tally is 0 goes on the counter: it is ready to cook. She cooks one dish from the counter, then walks down the board and crosses one mark off every dish that needed it. When a tally drops to 0, that dish moves to the counter too. If she ever looks at the board and the counter is empty while some dishes are still uncooked, those dishes are waiting for each other in a circle, and no cooking order exists.
For the wedding, the planner thinks the same way but with clocks: a task can start only when the last of its prerequisites is done, so she fills in "finish time" for each task in an order where every prerequisite is filled in first. That order is exactly the cook's order from the prep board.
Problem T1 · Festival Kitchen
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
A kitchen must cook n dishes, numbered 1 … n, one at a time. There are m rules; rule i says dish a_i must be cooked before dish b_i. Print an order of all n dishes that obeys every rule. If there are several, print the lexicographically smallest one. If no order works, print IMPOSSIBLE.
- Input: n and m (1 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_i b_i (1 ≤ a_i, b_i ≤ n).
- Output: n numbers separated by spaces, or
IMPOSSIBLE.
| Input | Output |
|---|---|
5 4 / 3 1 / 1 2 / 5 2 / 4 5 |
3 1 4 5 2 |
3 3 / 1 2 / 2 3 / 3 1 |
IMPOSSIBLE (1 before 2 before 3 before 1) |
4 3 / 1 2 / 2 3 / 3 2 |
IMPOSSIBLE (2 and 3 wait for each other) |
Smallest means: compare two orders like words in a dictionary. The first position where they differ decides. 3 1 4 5 2 < 3 4 1 5 2, because at the second position 1 < 4.
The graph. Each rule a b is an arrow, a directed edge a → b. An order in which every arrow points forward (from left to right) is a topological order. A directed graph has a topological order exactly when it has no cycle; such a graph is a DAG (directed acyclic graph).
The obvious attempt: every order (TLE)
next_permutation walks through all orders of 1 … n in increasing (dictionary) order, so the first order that obeys every rule is the smallest one. pos[x] is the position of dish x in the current order; a rule a b is broken if a comes after b.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> rule(m);
for (auto &[a, b] : rule) cin >> a >> b;
vector<int> p(n), pos(n + 1);
iota(p.begin(), p.end(), 1); // 1 2 3 ... n: smallest order first
do {
for (int i = 0; i < n; i++) pos[p[i]] = i;
bool ok = true;
for (auto [a, b] : rule) if (pos[a] > pos[b]) { ok = false; break; }
if (ok) { // the first valid order is the smallest
for (int x : p) cout << x << " ";
return 0;
}
} while (next_permutation(p.begin(), p.end()));
cout << "IMPOSSIBLE";
}
3 1 4 5 2
The three dishes in a circle:
IMPOSSIBLE
Both correct. Now only 13 dishes, where the rules force the exact reverse order 13 12 … 1 (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 13, m = 12; // only 13 dishes, built here
vector<pair<int, int>> rule;
for (int i = 1; i < n; i++) rule.push_back({i + 1, i}); // 13 before 12 before ...
vector<int> p(n), pos(n + 1);
iota(p.begin(), p.end(), 1); // 1 2 3 ... n: smallest order first
do {
for (int i = 0; i < n; i++) pos[p[i]] = i;
bool ok = true;
for (auto [a, b] : rule) if (pos[a] > pos[b]) { ok = false; break; }
if (ok) { // the first valid order is the smallest
for (int x : p) cout << x << " ";
return 0;
}
} while (next_permutation(p.begin(), p.end()));
cout << "IMPOSSIBLE";
}
Time Limit Exceeded (stopped after 8 seconds)
The only valid order, 13 12 … 1, is the very last permutation, so the loop checks all 13! = 6 227 020 800 orders, each with 12 rule checks. And the real limit is n = 2 · 10^5.
Kahn's algorithm: the prep board
indeg[v]= the number of arrows into v (the tally: how many dishes v still waits for).- Every dish with
indeg[v] == 0is ready: put it in a queue. - Repeat: take a ready dish u, append it to the order, and for every arrow u → v do
--indeg[v]; if it becomes 0, v is ready. - If the order has n dishes, it is a topological order. If it has fewer, the remaining dishes are on (or behind) a cycle:
IMPOSSIBLE.
Each dish enters the queue once and each arrow is crossed off once: O(n + m).
Why is the result valid? A dish v is taken only after its tally reached 0, which means every dish with an arrow into v was already taken. So every arrow points forward.
The first version uses a plain queue:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0); // unfinished prerequisites
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> ready;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.front();
ready.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) ready.push(v); // last prerequisite done
}
if ((int)order.size() < n) { cout << "IMPOSSIBLE\n"; return 0; }
for (int x : order) cout << x << " ";
}
3 4 1 5 2
Every rule is obeyed (3 before 1, 1 before 2, 5 before 2, 4 before 5), so the order is valid. But the expected answer is 3 1 4 5 2, which is smaller. Wrong Answer.
Always cook the smallest ready dish
Trace the sample (arrows 3 → 1, 1 → 2, 5 → 2, 4 → 5):
| Step | Ready dishes | Taken | Arrows crossed off | Order so far |
|---|---|---|---|---|
| start | {3, 4} | in-degrees: 1→1, 2→2, 5→1 | ||
| 1 | {3, 4} | 3 | 3 → 1: dish 1 becomes ready | 3 |
| 2 | {1, 4} | 1 | 1 → 2: dish 2 still waits for 5 | 3 1 |
| 3 | {4} | 4 | 4 → 5: dish 5 becomes ready | 3 1 4 |
| 4 | {5} | 5 | 5 → 2: dish 2 becomes ready | 3 1 4 5 |
| 5 | {2} | 2 | 3 1 4 5 2 |
At step 2 the plain queue took 4, because 4 had arrived first. To make the order as small as possible, the next dish must always be the smallest ready dish: any ready dish may legally go next, and putting a smaller number earlier always makes the order smaller. So the counter must be a min-heap: priority_queue<int, vector<int>, greater<int>> keeps the smallest element on top(). (A plain priority_queue<int> is a max-heap.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0); // unfinished prerequisites
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
priority_queue<int, vector<int>, greater<int>> ready; // smallest on top
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top();
ready.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) ready.push(v);
}
if ((int)order.size() < n) { cout << "IMPOSSIBLE\n"; return 0; } // a cycle
for (int x : order) cout << x << " ";
}
The sample, the three dishes in a circle, and dishes 2 and 3 waiting for each other:
3 1 4 5 2
IMPOSSIBLE
IMPOSSIBLE
On the second input no dish ever has in-degree 0, so the heap is empty from the start and the order has 0 < 3 dishes.
The forgotten cycle check
Delete the line if ((int)order.size() < n) { cout << "IMPOSSIBLE\n"; return 0; }:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0); // unfinished prerequisites
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
priority_queue<int, vector<int>, greater<int>> ready; // smallest on top
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top();
ready.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) ready.push(v);
}
for (int x : order) cout << x << " ";
}
Input 4 3 / 1 2 / 2 3 / 3 2:
1 4
Expected IMPOSSIBLE. Dishes 1 and 4 were ready and got cooked; dish 2 waits for 3 and dish 3 waits for 2, so neither tally ever reaches 0. The program happily prints a two-dish "order" for four dishes. Always compare order.size() with n.
The worst case
2 · 10^5 dishes and 2 · 10^5 rules, built inside the program: the rules only point from a smaller hidden rank to a larger one (so there is no cycle), and lab shuffles the dish numbers so the order is not simply 1 2 3 ….
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 200000, m = 200000; // worst case, built here
mt19937 rng(49);
vector<int> lab(n + 1);
iota(lab.begin(), lab.end(), 0);
shuffle(lab.begin() + 1, lab.end(), rng);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a = rng() % (n - 1) + 1, b = a + 1 + rng() % (n - a);
g[lab[a]].push_back(lab[b]);
indeg[lab[b]]++;
}
priority_queue<int, vector<int>, greater<int>> ready;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top();
ready.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) ready.push(v);
}
cout << order.size() << " dishes ordered\n";
}
200000 dishes ordered
About 0.09 seconds: n heap pushes and pops of O(log n) each, plus m arrow decrements, O((n + m) log n).
Stress test against every order
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> kahn(int n, vector<pair<int, int>> &r) {
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0), order;
for (auto [a, b] : r) g[a].push_back(b), indeg[b]++;
priority_queue<int, vector<int>, greater<int>> q;
for (int v = 1; v <= n; v++) if (!indeg[v]) q.push(v);
while (!q.empty()) {
int u = q.top();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
if ((int)order.size() < n) order.clear();
return order;
}
vector<int> brute(int n, vector<pair<int, int>> &r) {
vector<int> p(n), pos(n + 1);
iota(p.begin(), p.end(), 1);
do {
for (int i = 0; i < n; i++) pos[p[i]] = i;
bool ok = true;
for (auto [a, b] : r) ok &= pos[a] < pos[b];
if (ok) return p;
} while (next_permutation(p.begin(), p.end()));
return {};
}
int main() {
mt19937 rng(49);
for (int t = 1; t <= 500; t++) {
int n = rng() % 6 + 1, m = rng() % 7;
vector<pair<int, int>> r(m);
for (auto &[a, b] : r) { a = rng() % n + 1; b = rng() % n + 1; }
if (kahn(n, r) != brute(n, r)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
With n ≤ 6 and up to 6 random rules (a rule can even be a b with a = b, a self-loop), many of the 500 tests contain cycles; both functions return an empty vector for those. The brute force is surely correct (it literally tries every order from the smallest up), so agreement on 500 cases is strong evidence that the heap version is right, including the IMPOSSIBLE cases.
Problem T2 · Wedding Prep
(Written for this course, in the style of a Codeforces Div. 2 C problem.)
A wedding has n preparation tasks; task i takes t_i hours. There are m rules; rule a b means task a must finish before task b can start. The rules contain no cycle. There are unlimited helpers, so any number of tasks can run at the same time. Print the minimum number of hours until every task is done.
- Input: n and m (1 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then t_1 … t_n (1 ≤ t_i ≤ 10^9), then m lines a b. The graph is guaranteed to be a DAG.
- Output: the minimum total time.
| Input | Output |
|---|---|
5 5 / 3 2 4 1 5 / 4 1 / 1 2 / 3 2 / 2 5 / 4 5 |
11 (4 → 1 → 2 → 5: 1 + 3 + 2 + 5) |
1 0 / 7 |
7 |
3 0 / 4 9 2 |
9 (all three run at once) |
The recurrence. With unlimited helpers, a task starts the moment its last prerequisite finishes:
finish[v] = t[v] + max(finish[u] over all arrows u → v) (the max of nothing is 0)
and the answer is the largest finish[v]. Unrolled, finish[v] is the heaviest path (sum of task times) that ends at v, so the answer is the longest path in the DAG, also called the critical path of the project. (On a general graph with cycles the longest simple path is NP-hard; on a DAG it is easy, as we are about to see.)
The obvious attempt: plain recursion (TLE)
finish(v) asks every prerequisite for its finish time and takes the maximum:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> t;
vector<vector<int>> pre;
ll finish(int v) { // when can task v be done?
ll start = 0;
for (int u : pre[v]) start = max(start, finish(u));
return start + t[v];
}
int main() {
int n, m;
cin >> n >> m;
t.assign(n + 1, 0);
pre.assign(n + 1, {});
for (int i = 1; i <= n; i++) cin >> t[i];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
pre[b].push_back(a);
}
ll ans = 0;
for (int v = 1; v <= n; v++) ans = max(ans, finish(v));
cout << ans << "\n";
}
11
Correct. Now 120 tasks in 60 layers of two, where every task needs both tasks of the layer before (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> t;
vector<vector<int>> pre;
ll finish(int v) { // when can task v be done?
ll start = 0;
for (int u : pre[v]) start = max(start, finish(u));
return start + t[v];
}
int main() {
int n = 120; // 60 layers of 2 tasks, built here
t.assign(n + 1, 1);
pre.assign(n + 1, {});
for (int v = 3; v <= n; v++) // needs both tasks of the layer before
pre[v] = {(v - 1) / 2 * 2 - 1, (v - 1) / 2 * 2};
ll ans = 0;
for (int v = 1; v <= n; v++) ans = max(ans, finish(v));
cout << ans << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Each call to a task in layer k makes two calls into layer k − 1, so one call at the top layer becomes 2^59 calls at the bottom: about 10^18 calls. The graph has only 120 tasks; the recursion asks the same 120 questions again and again because it never remembers an answer.
DP: compute each finish once, in the right order
Dynamic programming stores f[v] = finish[v] and computes each one once. The only question is the order: when f[v] is computed, every f[u] with an arrow u → v must already be final. For the sample:
| Task (hours) | Waits for | f |
|---|---|---|
| 4 (1 h) | nothing | 1 |
| 3 (4 h) | nothing | 4 |
| 1 (3 h) | 4 | 1 + 3 = 4 |
| 2 (2 h) | 1, 3 | max(4, 4) + 2 = 6 |
| 5 (5 h) | 2, 4 | max(6, 1) + 5 = 11 |
The order 4, 3, 1, 2, 5 puts every prerequisite first: it is a topological order.
The shortcut that fails: index order (WA)
The tempting shortcut is to loop v = 1 … n:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> t(n + 1);
for (int i = 1; i <= n; i++) cin >> t[i];
vector<vector<int>> pre(n + 1), g(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b; // a must finish before b starts
pre[b].push_back(a);
g[a].push_back(b);
}
vector<ll> f(n + 1, 0);
ll ans = 0;
for (int v = 1; v <= n; v++) { // in index order
ll start = 0;
for (int u : pre[v]) start = max(start, f[u]);
f[v] = start + t[v];
ans = max(ans, f[v]);
}
cout << ans << "\n";
}
10
Expected 11. Follow the loop:
| v | Prerequisites and their f at that moment | f[v] |
|---|---|---|
| 1 | f[4] = 0 (task 4 not computed yet) | 0 + 3 = 3 (should be 4) |
| 2 | f[1] = 3, f[3] = 0 (task 3 not computed yet) | 3 + 2 = 5 (should be 6) |
| 3 | none | 4 |
| 4 | none | 1 |
| 5 | f[2] = 5, f[4] = 1 | 5 + 5 = 10 (should be 11) |
Task 1 needs task 4, but 4 is a bigger number, so f[4] was still 0 when f[1] was computed. Index order works only when every arrow goes from a smaller number to a larger one, and the input promises nothing like that.
DP in topological order (accepted)
Run Kahn (a plain queue is enough: any topological order works for the DP), then fill f in that order:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> t(n + 1);
for (int i = 1; i <= n; i++) cin >> t[i];
vector<vector<int>> pre(n + 1), g(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b; // a must finish before b starts
pre[b].push_back(a);
g[a].push_back(b);
}
vector<int> indeg(n + 1, 0), order;
for (int v = 1; v <= n; v++) indeg[v] = pre[v].size();
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> f(n + 1, 0);
ll ans = 0;
for (int v : order) { // prerequisites always come first
ll start = 0;
for (int u : pre[v]) start = max(start, f[u]);
f[v] = start + t[v];
ans = max(ans, f[v]);
}
cout << ans << "\n";
}
The sample, one task of seven hours, and three independent tasks:
11
7
9
The worst case and long long
2 · 10^5 tasks with hours up to 10^9, one long chain 1 → 2 → … → n through all of them, plus random extra arrows (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 200000, m = 200000; // worst case, built here
mt19937 rng(49);
vector<ll> t(n + 1);
for (int i = 1; i <= n; i++) t[i] = rng() % 1000000000 + 1;
vector<vector<int>> pre(n + 1), g(n + 1);
for (int v = 2; v <= n; v++) { // one long chain
pre[v].push_back(v - 1);
g[v - 1].push_back(v);
}
for (int i = n - 1; i < m; i++) {
int a = rng() % (n - 1) + 1, b = a + 1 + rng() % (n - a);
pre[b].push_back(a);
g[a].push_back(b);
}
vector<int> indeg(n + 1, 0), order;
for (int v = 1; v <= n; v++) indeg[v] = pre[v].size();
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> f(n + 1, 0);
ll ans = 0;
for (int v : order) { // prerequisites always come first
ll start = 0;
for (int u : pre[v]) start = max(start, f[u]);
f[v] = start + t[v];
ans = max(ans, f[v]);
}
cout << ans << "\n";
}
95266037688225
About 0.03 seconds, and the answer is about 10^14: the chain alone is the sum of 2 · 10^5 durations of up to 10^9, so f and the answer must be long long. Each task and each arrow is touched a constant number of times: O(n + m).
Stress test against the recursion
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 rng(49);
for (int it = 1; it <= 500; it++) {
int n = rng() % 8 + 1, m = rng() % 12;
vector<int> lab(n + 1);
iota(lab.begin(), lab.end(), 0);
shuffle(lab.begin() + 1, lab.end(), rng);
vector<ll> t(n + 1);
for (int i = 1; i <= n; i++) t[i] = rng() % 10 + 1;
vector<vector<int>> pre(n + 1), g(n + 1);
for (int i = 0; i < m && n > 1; i++) {
int a = rng() % (n - 1) + 1, b = a + 1 + rng() % (n - a);
pre[lab[b]].push_back(lab[a]);
g[lab[a]].push_back(lab[b]);
}
function<ll(int)> rec = [&](int v) {
ll s = 0;
for (int u : pre[v]) s = max(s, rec(u));
return s + t[v];
};
ll slow = 0;
for (int v = 1; v <= n; v++) slow = max(slow, rec(v));
vector<int> indeg(n + 1), order;
queue<int> q;
for (int v = 1; v <= n; v++) if (!(indeg[v] = pre[v].size())) q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (!--indeg[v]) q.push(v);
}
vector<ll> f(n + 1);
ll fast = 0;
for (int v : order) {
for (int u : pre[v]) f[v] = max(f[v], f[u]);
f[v] += t[v];
fast = max(fast, f[v]);
}
if (slow != fast) { cout << "mismatch on test " << it; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
The random DAGs are built the same way as above (arrows only from a smaller hidden rank to a larger one, then the labels are shuffled), so the index order is usually not a topological order; the recursion is slow but surely correct on 8 tasks.
Problem T3 · One-way Roads
(Written for this course.)
n towns and m one-way roads; road i goes from a_i to b_i. The roads contain no cycle. Two roads may join the same pair of towns (they count as different routes). Print the number of different routes from town 1 to town n, modulo 10^9 + 7.
- Input: n and m (2 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a b. The graph is a DAG.
- Output: the number of routes modulo 1 000 000 007.
| Input | Output |
|---|---|
4 5 / 1 2 / 1 3 / 2 3 / 2 4 / 3 4 |
3 (1 2 4, 1 3 4, 1 2 3 4) |
3 1 / 2 3 |
0 (no road leaves town 1) |
2 1 / 1 2 |
1 |
The recurrence. Every route into v arrives through its last road u → v, and different last roads give different routes. So
ways[v] = sum of ways[u] over all roads u → v, ways[1] = 1,
the same DP as T2 with a sum instead of a max. In topological order, ways[u] is final before it is used. Here the code pushes each town's count forward along its roads (ways[v] += ways[u] when u is taken), which is the same sum computed from the other side.
The obvious attempt: no modulo (WA)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> ways(n + 1, 0);
ways[1] = 1;
for (int u : order) // push u's count forward
for (int v : g[u]) ways[v] += ways[u];
cout << ways[n] << "\n";
}
3
Correct on the sample. Now 101 towns, where each step i → i + 1 has three parallel roads, so there are 3^100 routes (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 101; // 100 steps, 3 parallel roads each, built here
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 1; i < n; i++)
for (int k = 0; k < 3; k++) { g[i].push_back(i + 1); indeg[i + 1]++; }
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> ways(n + 1, 0);
ways[1] = 1;
for (int u : order) // push u's count forward
for (int v : g[u]) ways[v] += ways[u];
cout << ways[n] << "\n";
}
-2984622845537545263
A negative number of routes. 3^100 ≈ 5.2 · 10^47, and long long holds at most about 9.2 · 10^18; the additions overflowed many times over (signed overflow is undefined behaviour in C++; here it wrapped around modulo 2^64). Wrong Answer.
Modulo at every addition (accepted)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 101; // 100 steps, 3 parallel roads each, built here
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 1; i < n; i++)
for (int k = 0; k < 3; k++) { g[i].push_back(i + 1); indeg[i + 1]++; }
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> ways(n + 1, 0);
ways[1] = 1;
for (int u : order)
for (int v : g[u]) ways[v] = (ways[v] + ways[u]) % MOD; // mod at every step
cout << ways[n] << "\n";
}
886041711
That is 3^100 mod (10^9 + 7). Each ways[v] stays below 10^9 + 7, so the sum of two of them is below 2.1 · 10^9 and fits easily in long long before the %. The full program with input:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> ways(n + 1, 0);
ways[1] = 1;
for (int u : order)
for (int v : g[u]) ways[v] = (ways[v] + ways[u]) % MOD; // mod at every step
cout << ways[n] << "\n";
}
The sample, then the edge cases: town 1 has no road out (3 1 / 2 3), and two towns with one road (2 1 / 1 2):
3
0
1
In the second input, both town 1 and town 2 start with in-degree 0. Town 1 has no road, so its count of 1 goes nowhere; town 2 pushes ways[2] = 0 to town 3. Towns that cannot be reached from town 1 simply carry a count of 0, so no special case is needed.
Stress test against walking every route
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main() {
mt19937 rng(49);
for (int it = 1; it <= 500; it++) {
int n = rng() % 8 + 1, m = rng() % 14;
vector<int> lab(n + 1);
iota(lab.begin(), lab.end(), 0);
shuffle(lab.begin() + 1, lab.end(), rng);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m && n > 1; i++) {
int a = rng() % (n - 1) + 1, b = a + 1 + rng() % (n - a);
g[lab[a]].push_back(lab[b]);
indeg[lab[b]]++;
}
function<ll(int)> dfs = [&](int u) -> ll { // walk every route
if (u == n) return 1;
ll s = 0;
for (int v : g[u]) s += dfs(v);
return s;
};
queue<int> q;
vector<int> order;
for (int v = 1; v <= n; v++) if (!indeg[v]) q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (!--indeg[v]) q.push(v);
}
vector<ll> w(n + 1, 0);
w[1] = 1;
for (int u : order) for (int v : g[u]) w[v] = (w[v] + w[u]) % MOD;
if (dfs(1) % MOD != w[n]) { cout << "mismatch on test " << it; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
The DFS walks every route from 1 and counts the ones that reach n. On 8 towns and 13 roads the counts are small, so dfs(1) % MOD is exact.
Complexity vs the constraints
| Method | Time | Memory | Verdict |
|---|---|---|---|
every order (next_permutation) |
O(n! · m) | O(n + m) | TLE at n = 13 |
| Kahn with a queue | O(n + m) | O(n + m) | a valid order, but not the smallest (WA on T1) |
| Kahn with a min-heap | O((n + m) log n) | O(n + m) | accepted, 0.09 s at n = m = 2 · 10^5 |
| plain recursion for finish times | exponential (2^60 calls on 60 layers) | O(depth) | TLE |
| DP in index order | O(n + m) | O(n + m) | WA (10, not 11) |
| DP in topological order | O(n + m) | O(n + m) | accepted, 0.03 s at n = m = 2 · 10^5 |
| counting routes without mod | O(n + m) | O(n + m) | WA (overflow) |
counting routes with % MOD |
O(n + m) | O(n + m) | accepted |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| try every order | Time Limit Exceeded |
n! orders: 13! ≈ 6.2 · 10^9 | Kahn's algorithm |
a plain queue when the smallest order is asked |
3 4 1 5 2 (expected 3 1 4 5 2) |
4 arrived first, 1 is smaller | priority_queue<int, vector<int>, greater<int>> |
priority_queue<int> without greater |
4 5 3 1 2 (the largest order, homework 1) |
the default is a max-heap | add vector<int>, greater<int> |
no order.size() == n check |
1 4 (expected IMPOSSIBLE) |
dishes on a cycle never reach in-degree 0 | print IMPOSSIBLE when the order is short |
| recursion without storing answers | Time Limit Exceeded |
the same task is recomputed 2^60 times | DP: compute each value once |
| DP in index order | 10 (expected 11) |
a prerequisite had a bigger number | DP in topological order |
int finish times |
overflow on the worst case (answer 95266037688225) |
up to 2 · 10^14 hours, int stops at about 2.1 · 10^9 |
long long |
| counting routes without mod | -2984622845537545263 |
3^100 overflows long long |
% MOD at every addition |
Mini project
Write a DAG toolbox with topoOrder(n, edges, smallest) (returns the order or an empty vector on a cycle), longestPath(n, t, edges) (returns the time and the critical path itself), countPaths(n, edges, s, t) (mod 10^9 + 7) and findCycle(n, edges) (returns the dishes of one cycle when Kahn gets stuck: start from any dish left over and keep following an arrow to another leftover dish until a dish repeats). Use it on a real example: your semester's courses and their prerequisites, or the build steps of a small project (compile → link → test → package). Print the earliest semester for each course (the longest path in edges ending at it). Stress test every function against a brute force on tiny random graphs.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Largest order instead of smallest. Same input as Festival Kitchen; print the lexicographically largest valid order.
Solution
Use a max-heap (priority_queue<int> with no comparator) so the largest ready dish is always taken. The exchange argument is the same: any ready dish may go next, and putting a larger number earlier makes the order larger.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
priority_queue<int> ready; // max-heap: the largest ready dish on top
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top();
ready.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) ready.push(v);
}
if ((int)order.size() < n) { cout << "IMPOSSIBLE\n"; return 0; }
for (int x : order) cout << x << " ";
cout << "\n";
}
The episode's first two samples:
4 5 3 1 2
IMPOSSIBLE
(Careful with the related problem "make dish 1 as early as possible, then dish 2, …": that is not the smallest order. It is solved by running max-heap Kahn on the reversed arrows and reversing the result.)
2. Longest path counting edges, and print the path. n nodes, m arrows, a DAG. Print the largest number of arrows on a path, then one such path.
Solution
len[v] = the most arrows on a path ending at v, filled in topological order; par[v] remembers which node gave the best value. Walk par back from the node with the largest len, then reverse.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<int> len(n + 1, 0), par(n + 1, 0); // longest path (in edges) ending at v, and where it came from
for (int u : order)
for (int v : g[u])
if (len[u] + 1 > len[v]) { len[v] = len[u] + 1; par[v] = u; }
int end = 1;
for (int v = 1; v <= n; v++) if (len[v] > len[end]) end = v;
vector<int> path;
for (int v = end; v != 0; v = par[v]) path.push_back(v); // walk the parents back
reverse(path.begin(), path.end());
cout << len[end] << "\n";
for (int x : path) cout << x << " ";
cout << "\n";
}
The One-way Roads sample (4 5 / 1 2 / 1 3 / 2 3 / 2 4 / 3 4), and the Wedding Prep arrows without durations (5 5 / 4 1 / 1 2 / 3 2 / 2 5 / 4 5):
3
1 2 3 4
3
4 1 2 5
3. Shortest path in a DAG with negative weights. n nodes, m arrows a b w (w may be negative), a DAG, and a start s. Print the shortest distance from s to every node, or INF if it is unreachable.
Solution
In topological order, relax every arrow leaving u: dist[v] = min(dist[v], dist[u] + w). When u is taken, every arrow into u has already been relaxed, so dist[u] is final. Negative weights are no problem because there is no cycle (so no negative cycle). This is O(n + m), faster than Dijkstra (which fails with negative weights) and Bellman–Ford. Skip nodes with dist[u] == INF so that INF + w never overflows.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s; // shortest paths from s
vector<vector<pair<int, ll>>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
ll w;
cin >> a >> b >> w; // w may be negative
g[a].push_back({b, w});
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (auto [v, w] : g[u]) if (--indeg[v] == 0) q.push(v);
}
const ll INF = LLONG_MAX;
vector<ll> dist(n + 1, INF);
dist[s] = 0;
for (int u : order) {
if (dist[u] == INF) continue; // not reachable from s (yet, or ever)
for (auto [v, w] : g[u]) dist[v] = min(dist[v], dist[u] + w);
}
for (int v = 1; v <= n; v++) {
if (dist[v] == INF) cout << "INF ";
else cout << dist[v] << " ";
}
cout << "\n";
}
Input (first line n m s):
5 6 1
1 2 4
1 3 2
3 2 -5
2 4 1
3 4 6
5 4 1
0 -3 2 -2 INF
Node 2 is reached more cheaply through 3 (2 − 5 = −3) than directly (4), and node 5 cannot be reached from 1.
4. Is the topological order unique? Print YES if exactly one valid order exists, NO if several exist, and IMPOSSIBLE if none exists.
Solution
Run Kahn. If at any moment two or more dishes are ready at the same time, either of them could go next, so there are at least two orders. If the queue always holds exactly one dish, every step was forced and the order is unique (equivalently, the order is a path: every consecutive pair is joined by an arrow, a Hamiltonian path).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
int taken = 0;
bool unique = true;
while (!q.empty()) {
if (q.size() > 1) unique = false; // two dishes ready at once: either can go first
int u = q.front();
q.pop();
taken++;
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
if (taken < n) cout << "IMPOSSIBLE\n";
else cout << (unique ? "YES" : "NO") << "\n";
}
The Festival Kitchen sample (3 and 4 are ready together), a chain 4 3 / 1 2 / 2 3 / 3 4, and the three dishes in a circle:
NO
YES
IMPOSSIBLE
Quick quiz
Kahn's algorithm runs on 6 dishes and ends with order.size() == 4. What does it mean?
if ((int)order.size() < n)
cout << "IMPOSSIBLE";
A) Two dishes have no rules · B) There is a cycle · C) The answer has 4 dishes · D) The heap was empty at the start
Answer
B. Dishes on a cycle wait for each other, so their in-degrees never reach 0 and they are never taken (dishes that depend on a cycle are stuck too): the rules contain a cycle and the answer is IMPOSSIBLE. A dish with no rules has in-degree 0 and is taken immediately, and if the heap were empty at the start the order would have 0 dishes, not 4.
Interview questions
- What is a topological order, and when does one exist? An ordering of the nodes of a directed graph in which every edge u → v has u before v. It exists if and only if the graph has no directed cycle, that is, the graph is a DAG.
- Explain Kahn's algorithm and its complexity. Count in-degrees, put every node with in-degree 0 in a queue, repeatedly remove a node, append it to the order and decrement the in-degree of its out-neighbours, pushing those that reach 0. O(n + m); O((n + m) log n) with a heap for the lexicographically smallest order.
- How do you detect a cycle in a directed graph? Kahn's algorithm: if fewer than n nodes are output, there is a cycle. Alternatively, a DFS with three colours (unvisited, on the stack, finished): an edge to a node that is still on the stack closes a cycle.
- Give a DFS-based topological sort. Run DFS from every unvisited node and append each node to a list when it finishes; the reversed finish order is a topological order. Also O(n + m), but recursion depth can reach n, so in contests prefer Kahn (iterative) for n = 2 · 10^5.
- Why is the longest path easy on a DAG but hard in general? On a DAG, processing nodes in topological order guarantees every predecessor's value is final, giving O(n + m) DP. With cycles there is no such order, and the longest simple path problem is NP-hard (it contains the Hamiltonian path problem).
- How do you count paths between two nodes in a DAG? ways[s] = 1, then in topological order add ways[u] to ways[v] for each edge u → v, taking the result modulo a prime such as 10^9 + 7.
- Why can shortest paths in a DAG handle negative weights? Relaxing edges in topological order finalises each node before its out-edges are used, and with no cycles there is no negative cycle. O(n + m).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Directed edge (arrow) | An edge that can be used in one direction only, written a → b | rule "cook 3 before 1": 3 → 1 |
| Directed graph | A graph whose edges all have a direction | the kitchen rules |
| Topological order | An order of all nodes in which every edge points forward (from earlier to later) | 3 1 4 5 2 |
| Cycle (directed) | A path of arrows that returns to its start | 1 → 2 → 3 → 1 |
| DAG | Directed acyclic graph: a directed graph with no cycle; exactly the graphs that have a topological order | the wedding tasks |
| In-degree | The number of arrows coming into a node | dish 2 has in-degree 2 (from 1 and 5) |
| Out-degree | The number of arrows leaving a node | dish 4 has out-degree 1 |
| Adjacency list | For each node, the list of nodes its arrows point to | g[a].push_back(b) |
| Kahn's algorithm | Topological sort that repeatedly takes a node of in-degree 0 and lowers its neighbours' in-degrees | the prep board |
| Ready node | A node whose in-degree has dropped to 0: all its prerequisites are done | 3 and 4 at the start |
| Queue | First in, first out container | queue<int>: takes 4 before 1 |
| Min-heap | A container whose top is always the smallest element | priority_queue<int, vector<int>, greater<int>> |
| Max-heap | A container whose top is always the largest element; C++'s default priority_queue |
priority_queue<int> (homework 1) |
greater<int> |
The comparator that turns priority_queue into a min-heap |
smallest ready dish on top() |
| Lexicographically smallest | Smallest when compared like dictionary words: the first differing position decides | 3 1 4 5 2 < 3 4 1 5 2 |
IMPOSSIBLE |
The required output when no valid order exists (the rules contain a cycle) | 3 3 / 1 2 / 2 3 / 3 1 |
next_permutation |
Turns an array into the next order in dictionary order; false after the last one | the brute force for T1 |
| Factorial (n!) | The number of orders of n items: 1 · 2 · … · n | 13! = 6 227 020 800 |
| Recursion | A function that calls itself on smaller questions | finish(v) calls finish(u) |
| Exponential time | Time that doubles (or worse) with each step of input size | 2^60 calls |
| Dynamic programming (DP) | Computing each subproblem once, storing it, and building answers from stored values | f[v] |
| Memoization | Storing the answer of a recursive call so it is never computed twice | the fix for REC_BIG |
| DP on a DAG | DP where the states are nodes and the order of computation is a topological order | longest path, counting paths |
| Longest path | The path with the largest total weight (or number of edges) | 4 → 1 → 2 → 5: 11 hours |
| Critical path | The longest path in a project's task graph: it decides the earliest finish | the wedding answer |
| Push vs pull DP | Pull: f[v] reads its predecessors; push: u adds its value to its successors | T2 pulls, T3 pushes |
| Relaxation | Improving a stored distance with dist[v] = min(dist[v], dist[u] + w) |
homework 3 |
| Parent array | par[v] = the node the best path to v came from; used to rebuild the path |
homework 2 |
| Unique topological order | Exactly one valid order: the queue never holds two nodes at once | homework 4 |
| Modulo 10^9 + 7 | Keeping a huge count as its remainder after dividing by the prime 1 000 000 007 | 3^100 → 886041711 |
| Overflow | A value larger than the type can hold; signed overflow is undefined behaviour and here wrapped around | -2984622845537545263 |
long long |
64-bit integer, up to about 9.2 · 10^18 | 95266037688225 |
| Brute force | Trying every possibility; slow but surely correct | every order, every route |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random small inputs | all 500 tests passed |
mt19937 |
C++'s Mersenne Twister random number generator, seeded for repeatable tests | mt19937 rng(49) |
| Worst case | The largest, hardest input the constraints allow | n = m = 2 · 10^5 |
| Time Limit Exceeded (TLE) | The program ran longer than the limit (8 seconds on the SyntaxPilot compiler) | 13! orders, 2^60 calls |
| Wrong Answer (WA) | The program finished but printed the wrong output | 3 4 1 5 2, 1 4, 10 |
| Accepted | Correct output within the time limit | min-heap Kahn |
Summary
- Rules "a before b" are directed edges; an order with every arrow pointing forward is a topological order, and it exists exactly when the graph is a DAG.
- Trying every order is n!: TLE at n = 13.
- Kahn's algorithm: count in-degrees, take nodes whose in-degree is 0, lower the in-degrees of their neighbours. O(n + m).
- For the smallest order, the ready set must be a min-heap (
greater<int>):3 1 4 5 2, not3 4 1 5 2. - order.size() < n means a cycle: print
IMPOSSIBLE, not1 4. - On a DAG, the topological order is the DP order: max for the longest path (
11, not the index-order10), sum for counting paths. - Counts grow exponentially: % MOD at every addition (
886041711, not-2984622845537545263); times grow to 10^14: long long.
Solutions in C++, Java and Python
Problem T1 · Festival Kitchen
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0); // unfinished prerequisites
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
priority_queue<int, vector<int>, greater<int>> ready; // smallest on top
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top();
ready.pop();
order.push_back(u);
for (int v : g[u])
if (--indeg[v] == 0) ready.push(v);
}
if ((int)order.size() < n) { cout << "IMPOSSIBLE\n"; return 0; } // a cycle
for (int x : order) cout << x << " ";
}
Java (adjacency list stored in arrays; PriorityQueue is a min-heap by default)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
st.nextToken(); int m = (int) st.nval;
int[] head = new int[n + 1], nxt = new int[m], to = new int[m], indeg = new int[n + 1];
Arrays.fill(head, -1);
for (int i = 0; i < m; i++) {
st.nextToken(); int a = (int) st.nval;
st.nextToken(); int b = (int) st.nval;
to[i] = b; nxt[i] = head[a]; head[a] = i; // adjacency list in arrays
indeg[b]++;
}
PriorityQueue<Integer> ready = new PriorityQueue<>(); // min-heap by default
for (int v = 1; v <= n; v++) if (indeg[v] == 0) ready.add(v);
int[] order = new int[n];
int cnt = 0;
while (!ready.isEmpty()) {
int u = ready.poll();
order[cnt++] = u;
for (int e = head[u]; e != -1; e = nxt[e])
if (--indeg[to[e]] == 0) ready.add(to[e]);
}
if (cnt < n) { System.out.println("IMPOSSIBLE"); return; } // a cycle
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(order[i]).append(' ');
System.out.println(sb.toString().trim());
}
}
3 1 4 5 2
IMPOSSIBLE
IMPOSSIBLE
Python
import sys
import heapq
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
g[a].append(b)
indeg[b] += 1
ready = [v for v in range(1, n + 1) if indeg[v] == 0]
heapq.heapify(ready) # min-heap: smallest ready dish first
order = []
while ready:
u = heapq.heappop(ready)
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(ready, v)
if len(order) < n: # a cycle
print("IMPOSSIBLE")
else:
print(" ".join(map(str, order)))
main()
3 1 4 5 2
IMPOSSIBLE
IMPOSSIBLE
Problem T2 · Wedding Prep
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> t(n + 1);
for (int i = 1; i <= n; i++) cin >> t[i];
vector<vector<int>> pre(n + 1), g(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b; // a must finish before b starts
pre[b].push_back(a);
g[a].push_back(b);
}
vector<int> indeg(n + 1, 0), order;
for (int v = 1; v <= n; v++) indeg[v] = pre[v].size();
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> f(n + 1, 0);
ll ans = 0;
for (int v : order) { // prerequisites always come first
ll start = 0;
for (int u : pre[v]) start = max(start, f[u]);
f[v] = start + t[v];
ans = max(ans, f[v]);
}
cout << ans << "\n";
}
Java (Kahn and the DP in one pass: when u leaves the queue its start time is final, so its finish is pushed forward to every task that waits for it)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
st.nextToken(); int m = (int) st.nval;
long[] t = new long[n + 1];
for (int i = 1; i <= n; i++) { st.nextToken(); t[i] = (long) st.nval; }
int[] head = new int[n + 1], nxt = new int[m], to = new int[m], indeg = new int[n + 1];
Arrays.fill(head, -1);
for (int i = 0; i < m; i++) {
st.nextToken(); int a = (int) st.nval;
st.nextToken(); int b = (int) st.nval;
to[i] = b; nxt[i] = head[a]; head[a] = i;
indeg[b]++;
}
int[] q = new int[n]; // Kahn with an array as the queue
int qh = 0, qt = 0;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q[qt++] = v;
long[] start = new long[n + 1]; // latest finish among prerequisites
long ans = 0;
while (qh < qt) {
int u = q[qh++];
long f = start[u] + t[u]; // all prerequisites of u are final
ans = Math.max(ans, f);
for (int e = head[u]; e != -1; e = nxt[e]) {
int v = to[e];
start[v] = Math.max(start[v], f); // push u's finish forward
if (--indeg[v] == 0) q[qt++] = v;
}
}
System.out.println(ans);
}
}
11
7
9
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
t = [0] + [int(x) for x in data[2:2 + n]]
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
pos = 2 + n
for _ in range(m):
a, b = int(data[pos]), int(data[pos + 1])
pos += 2
g[a].append(b)
indeg[b] += 1
q = [v for v in range(1, n + 1) if indeg[v] == 0] # a list used as a queue
start = [0] * (n + 1)
ans = 0
i = 0
while i < len(q):
u = q[i]
i += 1
f = start[u] + t[u] # every prerequisite of u is already done
if f > ans:
ans = f
for v in g[u]:
if f > start[v]:
start[v] = f
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
print(ans)
main()
11
7
9
Problem T3 · One-way Roads
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
indeg[b]++;
}
queue<int> q;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
vector<ll> ways(n + 1, 0);
ways[1] = 1;
for (int u : order)
for (int v : g[u]) ways[v] = (ways[v] + ways[u]) % MOD; // mod at every step
cout << ways[n] << "\n";
}
Java
import java.io.*;
import java.util.*;
public class Main {
static final long MOD = 1_000_000_007L;
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
st.nextToken(); int m = (int) st.nval;
int[] head = new int[n + 1], nxt = new int[m], to = new int[m], indeg = new int[n + 1];
Arrays.fill(head, -1);
for (int i = 0; i < m; i++) {
st.nextToken(); int a = (int) st.nval;
st.nextToken(); int b = (int) st.nval;
to[i] = b; nxt[i] = head[a]; head[a] = i;
indeg[b]++;
}
int[] q = new int[n];
int qh = 0, qt = 0;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q[qt++] = v;
long[] ways = new long[n + 1];
ways[1] = 1;
while (qh < qt) {
int u = q[qh++];
for (int e = head[u]; e != -1; e = nxt[e]) {
int v = to[e];
ways[v] = (ways[v] + ways[u]) % MOD; // mod at every step
if (--indeg[v] == 0) q[qt++] = v;
}
}
System.out.println(ways[n]);
}
}
3
0
1
Python
import sys
MOD = 1_000_000_007
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
g[a].append(b)
indeg[b] += 1
q = [v for v in range(1, n + 1) if indeg[v] == 0]
ways = [0] * (n + 1)
ways[1] = 1
i = 0
while i < len(q):
u = q[i]
i += 1
for v in g[u]:
ways[v] = (ways[v] + ways[u]) % MOD # mod at every step
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
print(ways[n])
main()
3
0
1