These are the notes for Competitive Programming episode 51, the seventh episode of the graphs section. One-way roads are back, and now they can go round in circles. One-way Zones splits a city into zones where everyone can reach everyone: a BFS from every junction is correct but Time Limit Exceeded at 2 · 10^4 junctions. A surveyor who writes each junction down when he has finished everything beyond it, then flips every one-way sign, is Kosaraju's algorithm: two DFS passes, O(n + m). Running the second pass in junction-number order prints 1 zone where the answer is 3; reverse finish order is right. Shift Requests asks for a schedule of morning and evening shifts that keeps every request of the form "a gets s or b gets t": trying all 2^n schedules is TLE at n = 40, while turning each request into two "if not this, then that" arrows gives the implication graph, and Kosaraju on it solves 2-SAT in linear time. A flipped comparison is caught by a self-check (request 1 broken!). Two 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
A surveyor has to map a city of one-way streets for the council, which wants to split it into zones: inside a zone you can drive from any junction to any other and back, obeying every sign. He explores depth-first: he keeps driving to junctions he has not seen, and when every road out of a junction leads somewhere he has already finished, he writes that junction in his notebook and backs up. The last junction in his notebook is special: it lies in a top zone, one that no other zone drives into.
Then he does something odd: he imagines every one-way sign flipped. A zone is still a zone (inside it you could already go both ways), but the roads that used to lead out of the top zone now point into it, so from the top zone, on flipped roads, he can never get out. One drive collects exactly one zone. He crosses it off, takes the next junction from the end of his notebook that is not yet crossed off, and drives again.
Problem Z1 · One-way Zones
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
A city has n junctions and m one-way roads; road i goes from a_i to b_i. Two junctions belong to the same zone if each can be reached from the other along the roads. Split the city into zones.
- 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; loops and repeated roads are allowed).
- Output: the number of zones c, then c lines, one per zone, listing its junctions in increasing order. Zones are printed in increasing order of their smallest junction.
| Input | Output |
|---|---|
6 7 / 4 5 / 5 6 / 6 4 / 6 2 / 2 3 / 3 2 / 3 1 |
3 / 1 / 2 3 / 4 5 6 |
3 0 |
3 / 1 / 2 / 3 |
4 4 / 1 2 / 2 3 / 3 4 / 4 1 |
1 / 1 2 3 4 |
Same zone means both ways. u and v share a zone exactly when u reaches v and v reaches u. This relation is reflexive, symmetric and transitive (if u ⇄ v and v ⇄ w then u ⇄ w), so it splits the junctions into classes: the strongly connected components (SCCs). In the first sample, 4 → 5 → 6 → 4 is a loop, 2 ⇄ 3, and 1 is a dead end that nobody can leave.
The obvious attempt: a BFS from every junction (TLE)
Run a BFS from every junction to learn its reach set R[v], then put u in v's zone when R[v][u] && R[u][v].
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g;
vector<bool> reach(int s) { // BFS: who can s reach?
vector<bool> seen(n + 1, false);
queue<int> q;
q.push(s);
seen[s] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : g[v]) if (!seen[u]) { seen[u] = true; q.push(u); }
}
return seen;
}
int main() {
cin >> n >> m;
g.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
vector<vector<bool>> R(n + 1);
for (int v = 1; v <= n; v++) R[v] = reach(v); // n BFS runs
vector<int> comp(n + 1, 0);
int c = 0;
for (int v = 1; v <= n; v++) {
if (comp[v]) continue;
c++;
for (int u = v; u <= n; u++)
if (R[v][u] && R[u][v]) comp[u] = c; // both ways: same zone
}
vector<vector<int>> zones(c + 1);
for (int v = 1; v <= n; v++) zones[comp[v]].push_back(v);
sort(zones.begin() + 1, zones.end()); // by smallest junction
cout << c << "\n";
for (int z = 1; z <= c; z++) {
for (int v : zones[z]) cout << v << " ";
cout << "\n";
}
}
3
1
2 3
4 5 6
Correct. Now 2 · 10^4 junctions on a ring plus random roads, 2 · 10^5 roads in all (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g;
vector<bool> reach(int s) { // BFS: who can s reach?
vector<bool> seen(n + 1, false);
queue<int> q;
q.push(s);
seen[s] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : g[v]) if (!seen[u]) { seen[u] = true; q.push(u); }
}
return seen;
}
int main() {
n = 20000, m = 200000; // a ring + random roads, built here
mt19937 rng(51);
g.assign(n + 1, {});
for (int v = 1; v <= n; v++) g[v].push_back(v % n + 1);
for (int i = n; i < m; i++) g[rng() % n + 1].push_back(rng() % n + 1);
vector<vector<bool>> R(n + 1);
for (int v = 1; v <= n; v++) R[v] = reach(v); // n BFS runs
vector<int> comp(n + 1, 0);
int c = 0;
for (int v = 1; v <= n; v++) {
if (comp[v]) continue;
c++;
for (int u = v; u <= n; u++)
if (R[v][u] && R[u][v]) comp[u] = c; // both ways: same zone
}
cout << c << " zones\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Each BFS walks up to n + m = 2.2 · 10^5 junctions and roads, and there are 2 · 10^4 of them: about 4.4 · 10^9 steps, plus a 2 · 10^4 × 2 · 10^4 reach table (4 · 10^8 bits). The real limit has ten times more junctions, which would also need 4 · 10^10 bits of memory.
Kosaraju's algorithm
- Pass 1. DFS over the original roads, starting from every unvisited junction in turn. When a junction finishes (all its roads have been explored), append it to
order. This is the finish order. - Build the reversed graph
rg: every road a → b becomes b → a. - Pass 2. Go through
orderfrom the end (last finished first). Every junction not yet in a zone starts a DFS on the reversed roads; everything it reaches that has no zone yet is one new zone.
On the first sample, pass 1 starts at 1. Junction 1 has no outgoing road, so it finishes first. From 2: 3 finishes (its roads go to 2 and 1, both already seen), then 2. From 4: 4 → 5 → 6, and 6 finishes (4 is open, 2 is done), then 5, then 4.
| Step | Pass 1 finish order | Pass 2 (flipped roads) |
|---|---|---|
| 1 | 1 | start at 4: 4 → 6 → 5, zone A = {4, 5, 6} |
| 2 | 1 3 2 | next unmarked from the end: 2 → 3 (6 is marked), zone B = {2, 3} |
| 3 | 1 3 2 6 5 4 | then 1, zone C = {1} |
Junction 4 finished last and sits in the top zone A: no road from outside enters {4, 5, 6}. On flipped roads, A's only exit (6 → 2) points into A, so the drive from 4 stays inside A.
The tempting shortcut: pass 2 by junction number (WA)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int v = 1; v <= n; v++) // second pass, by number
if (!comp[v]) dfs2(v, ++c);
vector<vector<int>> zones(c + 1);
for (int v = 1; v <= n; v++) zones[comp[v]].push_back(v);
sort(zones.begin() + 1, zones.end()); // by smallest junction
cout << c << "\n";
for (int z = 1; z <= c; z++) {
for (int v : zones[z]) cout << v << " ";
cout << "\n";
}
}
1
1 2 3 4 5 6
Expected 3. Junction 1 lies in a bottom zone: everybody can drive to it, so on the flipped roads it can climb into every zone above it (1 → 3 → 2 → 6 → 5 → 4), and the first drive swallows the whole city. The order of pass 2 is the whole trick.
The fix: last finished first
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) { // last finished first
int v = order[i];
if (!comp[v]) dfs2(v, ++c);
}
vector<vector<int>> zones(c + 1);
for (int v = 1; v <= n; v++) zones[comp[v]].push_back(v);
sort(zones.begin() + 1, zones.end()); // by smallest junction
cout << c << "\n";
for (int z = 1; z <= c; z++) {
for (int v : zones[z]) cout << v << " ";
cout << "\n";
}
}
The three samples: the sample city, three junctions with no roads, and a one-way ring of four.
3
1
2 3
4 5 6
3
1
2
3
1
1 2 3 4
The worst case
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
n = 100000, m = 200000; // worst case, built here
mt19937 rng(51);
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) { // last finished first
int v = order[i];
if (!comp[v]) dfs2(v, ++c);
}
vector<int> sz(c + 1, 0);
for (int v = 1; v <= n; v++) sz[comp[v]]++;
cout << c << " zones, largest " << *max_element(sz.begin(), sz.end()) << "\n";
}
36631 zones, largest 63370
About a tenth of a second on this machine, including start-up. A random one-way graph with twice as many roads as junctions has one giant zone and many single-junction zones around it.
Recursion depth. Both DFS functions are recursive, and a city that is one long road 1 → 2 → … → 2 · 10^5 makes them 2 · 10^5 calls deep. On judges with a large stack (Codeforces, AtCoder) this is fine. On this machine, with the default 8 MB stack, the program above stops with Segmentation fault on a 2 · 10^5-junction ring and works after ulimit -s unlimited. If your judge has a small stack, use the iterative DFS of the Java and Python solutions below; in Java and Python it is required anyway.
Why Kosaraju works
Write fin(v) for the position of v in the finish order, and for a zone C let fin(C) be the largest fin(v) over v in C (the last junction of C to finish).
Claim. If some road goes from zone C to a different zone D, then fin(C) > fin(D).
Proof. Look at the first junction x of C ∪ D that pass 1 visits.
- If x is in C: when x is entered, nothing in C ∪ D has been visited, and x reaches every junction of C and of D (through the road C → D). The DFS does not finish x until everything reachable from it through unvisited junctions is finished, so all of D finishes before x: fin(C) ≥ fin(x) > fin(D).
- If x is in D: D cannot reach C (otherwise C and D would be one zone), so the DFS from x finishes all of D without ever touching C. C is visited later, so every junction of C finishes after all of D: fin(C) > fin(D). ∎
Consequence 1: the last finished junction lies in a source zone. The zone with the largest fin has no road coming in from another zone (that zone would have a larger fin). It is a source component.
Consequence 2: in the reversed graph it is a sink. Flipping every road keeps every zone (both-way reachability does not care about direction) but turns every road into the source zone into a road out of it. A source of the original graph is a sink of the reversed one: a DFS from it on the flipped roads reaches exactly its own zone.
Consequence 3: the rest follows by induction. Remove that zone. Among the junctions left, the one that finished last is again in a zone with no road coming in from the zones that are left, and every flipped road out of it leads only into zones already marked, which pass 2 skips. So each drive of pass 2 collects exactly one zone, and the zones come out in topological order of the condensation: zone 1 has no incoming roads, and every road between zones goes from a smaller zone number to a bigger one. 2-SAT relies on this numbering below.
Pass 1 sees each junction and road once, the reversal is one more pass over the roads, and pass 2 sees each once more: O(n + m).
The condensation DAG
Shrink each zone to a single dot and keep one arrow for every road between two different zones. This condensation never has a cycle: a cycle of zones would let all of them reach each other, so they would be one zone. It is a DAG, and everything from episode 49 (topological order, DP on a DAG, longest paths) works on it. For the first sample:
zone A {4, 5, 6} --(6 -> 2)--> zone B {2, 3} --(3 -> 1)--> zone C {1}
source sink
Kosaraju numbers them A = 1, B = 2, C = 3: arrows go from smaller numbers to bigger ones. Practice problems 1 and 2 below are both "build the condensation, then work on the DAG".
Stress test against a search from every junction
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg;
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
}
vector<bool> reach(int s) {
vector<bool> seen(n + 1, false);
vector<int> st = {s};
seen[s] = true;
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int u : g[v]) if (!seen[u]) seen[u] = true, st.push_back(u);
}
return seen;
}
int main() {
mt19937 rng(51);
for (int t = 1; t <= 500; t++) {
n = rng() % 8 + 1, m = rng() % 14;
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1;
g[a].push_back(b);
rg[b].push_back(a);
}
order.clear();
seen.assign(n + 1, false);
comp.assign(n + 1, 0);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = n - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
vector<vector<bool>> R(n + 1);
for (int v = 1; v <= n; v++) R[v] = reach(v);
for (int a = 1; a <= n; a++)
for (int b = 1; b <= n; b++)
if ((comp[a] == comp[b]) != (R[a][b] && R[b][a])) {
cout << "mismatch on test " << t;
return 0;
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem Z2 · Shift Requests
(Written for this course, in the style of a Codeforces Div. 2 E problem.)
A festival has n volunteers. Each volunteer works exactly one shift: morning (M) or evening (E). There are m requests; request k says "volunteer a_k gets shift s_k, or volunteer b_k gets shift t_k" (at least one of the two must come true; a_k may equal b_k). Find any schedule that keeps every request, or report that none exists.
- Input: n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_k s_k b_k t_k, where s_k, t_k are
MorE. - Output: n letters separated by spaces (the shift of volunteer 1, 2, …, n), or
IMPOSSIBLE. Any valid schedule is accepted.
| Input | Output |
|---|---|
3 4 / 2 M 1 M / 3 E 1 E / 1 E 2 M / 1 M 2 E |
M M E (any valid schedule) |
1 2 / 1 M 1 M / 1 E 1 E |
IMPOSSIBLE (volunteer 1 must take both shifts) |
2 1 / 1 E 1 E |
E M (volunteer 2 can take either shift) |
This is 2-SAT: every volunteer is a true/false variable ("gets E"), every request is a clause of two literals joined by OR, and the question is whether all clauses can be made true at once.
The obvious attempt: every schedule (TLE)
Each schedule is a bitmask: bit i set means volunteer i + 1 works evenings. A literal is stored as 2 * (v - 1) + (s == 'E'), so x / 2 is the volunteer and x & 1 the shift.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<array<int, 2>> req(m);
auto lit = [](int v, char s) { return 2 * (v - 1) + (s == 'E'); }; // M: even, E: odd
for (auto &[x, y] : req) {
int a, b;
char s, t;
cin >> a >> s >> b >> t;
x = lit(a, s), y = lit(b, t); // a gets s OR b gets t
}
for (ll mask = 0; mask < (1LL << n); mask++) { // bit i set: volunteer i+1 gets E
auto holds = [&](int x) { return (mask >> (x / 2) & 1) == (x & 1); };
bool ok = true;
for (auto [x, y] : req) ok = ok && (holds(x) || holds(y));
if (ok) {
for (int i = 0; i < n; i++) cout << (mask >> i & 1 ? 'E' : 'M') << " ";
return 0;
}
}
cout << "IMPOSSIBLE";
}
M M E
Correct. Now only 40 volunteers, built so that the only valid schedule is the very last mask (request i says "i gets E or i + 1 gets M", and the last volunteer asked for E, which forces everyone to E):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 40, m = 40; // only 40 volunteers, built here
vector<array<int, 2>> req(m);
for (int i = 0; i + 1 < n; i++) req[i] = {2 * i + 1, 2 * (i + 1)}; // i: E, or i+1: M
req[n - 1] = {2 * n - 1, 2 * n - 1}; // the last one asked for E
for (ll mask = 0; mask < (1LL << n); mask++) { // bit i set: volunteer i+1 gets E
auto holds = [&](int x) { return (mask >> (x / 2) & 1) == (x & 1); };
bool ok = true;
for (auto [x, y] : req) ok = ok && (holds(x) || holds(y));
if (ok) {
for (int i = 0; i < n; i++) cout << (mask >> i & 1 ? 'E' : 'M') << " ";
return 0;
}
}
cout << "IMPOSSIBLE";
}
Time Limit Exceeded (stopped after 8 seconds)
2^40 ≈ 1.1 · 10^12 schedules, each checked against 40 requests. The real limit is n = 10^5.
Every request is two arrows
Make two nodes per volunteer: "v gets M" (node 2(v − 1)) and "v gets E" (node 2(v − 1) + 1). Exactly one of them will be true, and x ^ 1 is the opposite of node x.
A request "x or y" says: if x is false, y must be true, and if y is false, x must be true. So it adds two arrows:
x ^ 1 → y(not x forces y),y ^ 1 → x(not y forces x).
For "1 gets M or 2 gets M": "1 gets E → 2 gets M" and "2 gets E → 1 gets M". Following arrows means "this choice forces that choice". This directed graph is the implication graph. It is skew-symmetric: whenever p → q is an arrow, so is ¬q → ¬p (each request adds exactly such a pair), so a path p ⇝ q always comes with a path ¬q ⇝ ¬p.
IMPOSSIBLE test. If "v gets M" and "v gets E" are in the same SCC, then M forces E and E forces M: whichever shift v gets, it forces the other one too. No schedule exists. In the second sample, request "1 M or 1 M" adds 1E → 1M twice and request "1 E or 1 E" adds 1M → 1E: one zone, IMPOSSIBLE. The converse is also true, and the proof is in the next section: if no volunteer has M and E in one SCC, a schedule always exists.
Why the later zone wins
Run Kosaraju on the 2n nodes. Its zone numbers follow the arrows: every arrow goes from a smaller zone number to a bigger one (or stays inside a zone). For each volunteer, the M node and the E node are in different zones, so pick the shift whose zone number is bigger, the one that comes later.
Why it is safe. Say we pick literal p because comp[p] > comp[¬p].
- p cannot force ¬p: a path p ⇝ ¬p would give comp[p] ≤ comp[¬p].
- More strongly, nothing p forces gets broken. Suppose p is picked and p → q is an arrow. Then comp[p] ≤ comp[q]. By skew-symmetry ¬q → ¬p is also an arrow, so comp[¬q] ≤ comp[¬p]. Put together: comp[¬q] ≤ comp[¬p] < comp[p] ≤ comp[q], so comp[q] > comp[¬q] and q is picked too.
So the set of picked literals is closed under the arrows. If some request "x or y" were broken, ¬x and ¬y would both be picked; but ¬x → y is an arrow, so y would be picked as well. Contradiction: every request is kept.
Why the earlier one is dangerous. The earlier literal may have a path of arrows to its own opposite. Picking it starts a chain of forced choices that ends by demanding the shift we did not pick. That is exactly what the flipped comparison below does.
On the first sample the arrows are 1M → 3E, 1M → 2M, 1E → 2M, 1E → 2E, 2M → 1M, 2E → 1M, 2E → 1E, 3M → 1E. The SCCs in Kosaraju's order are {3M}, {1E, 2E}, {1M, 2M}, {3E}. The later zone gives 1: M, 2: M, 3: E.
The flipped comparison (caught by the self-check)
The code builds the arrows and their flipped copies, runs Kosaraju, answers IMPOSSIBLE when comp[2 * i] == comp[2 * i + 1], and at the end checks every request against the schedule it is about to print. Here, someone wrote < instead of >:
#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<array<int, 2>> req(m);
auto lit = [](int v, char s) { return 2 * (v - 1) + (s == 'E'); }; // M: even, E: odd
for (auto &[x, y] : req) {
int a, b;
char s, t;
cin >> a >> s >> b >> t;
x = lit(a, s), y = lit(b, t); // a gets s OR b gets t
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] < comp[2 * i + 1] ? 'M' : 'E';
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
if (ans[x / 2] != "ME"[x & 1] && ans[y / 2] != "ME"[y & 1]) {
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
for (char ch : ans) cout << ch << " ";
}
request 1 broken!
It picked the earlier zones: E E M. Request 1, "2 gets M or 1 gets M", is broken. The self-check caught it before the judge did. A self-check costs O(m) and turns a silent Wrong Answer into a visible message; keep it while developing (and printing nothing but the answer at the end is still fine, since a correct solution never triggers it).
The fix: pick the later zone
#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<array<int, 2>> req(m);
auto lit = [](int v, char s) { return 2 * (v - 1) + (s == 'E'); }; // M: even, E: odd
for (auto &[x, y] : req) {
int a, b;
char s, t;
cin >> a >> s >> b >> t;
x = lit(a, s), y = lit(b, t); // a gets s OR b gets t
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
if (ans[x / 2] != "ME"[x & 1] && ans[y / 2] != "ME"[y & 1]) {
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
for (char ch : ans) cout << ch << " ";
}
The three samples:
M M E
IMPOSSIBLE
E M
Volunteer 2 in the third sample has no requests, so E M and E E are both valid; the program happens to print E M.
The forty volunteers that broke the brute force
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 40, m = 40; // the same 40 volunteers
vector<array<int, 2>> req(m);
for (int i = 0; i + 1 < n; i++) req[i] = {2 * i + 1, 2 * (i + 1)}; // i: E, or i+1: M
req[n - 1] = {2 * n - 1, 2 * n - 1}; // the last one asked for E
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
if (ans[x / 2] != "ME"[x & 1] && ans[y / 2] != "ME"[y & 1]) {
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
for (char ch : ans) cout << ch << " ";
}
E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E
Instant, and the only possible schedule: the last request adds the arrow "40 gets M → 40 gets E", so 40 must take E, and the arrows "40 gets E → 39 gets E → … → 1 gets E" push everyone to evenings.
The worst case
A hidden random schedule is drawn first, and any request it would break gets its first literal flipped, so the instance is guaranteed to be solvable:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 100000, m = 200000; // worst case, built here
mt19937 rng(51);
vector<int> secret(n); // a hidden valid schedule
for (int &s : secret) s = rng() % 2;
vector<array<int, 2>> req(m);
for (auto &[x, y] : req) {
int a = rng() % n, b = rng() % n;
x = 2 * a + int(rng() % 2), y = 2 * b + int(rng() % 2);
if (x % 2 != secret[a] && y % 2 != secret[b]) x ^= 1; // keep it solvable
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
if (ans[x / 2] != "ME"[x & 1] && ans[y / 2] != "ME"[y & 1]) {
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
cout << "all " << m << " requests kept\n";
}
all 200000 requests kept
About 0.3 s on this machine: 2 · 10^5 nodes and 4 · 10^5 arrows. The schedule it finds need not be the hidden one; the self-check proves it is valid.
Stress test: brute force decides, the self-check verifies
On 500 tiny random cases, the brute force decides whether any schedule exists; the fast solution must agree, and every schedule it prints must keep every request.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 rng(51);
for (int t = 1; t <= 500; t++) {
int n = rng() % 6 + 1, m = rng() % 10;
vector<array<int, 2>> req(m);
for (auto &[x, y] : req) x = rng() % (2 * n), y = rng() % (2 * n);
bool can = false; // brute force: any schedule?
for (int mask = 0; mask < (1 << n) && !can; mask++) {
bool ok = true;
for (auto [x, y] : req)
ok = ok && ((mask >> (x / 2) & 1) == (x & 1) || (mask >> (y / 2) & 1) == (y & 1));
can = ok;
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) ans = "X";
if (ans == "X") break;
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E';
}
bool fast = ans != "X";
bool valid = true;
if (fast)
for (auto [x, y] : req)
valid = valid && (ans[x / 2] == "ME"[x & 1] || ans[y / 2] == "ME"[y & 1]);
if (fast != can || !valid) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Memory | Verdict |
|---|---|---|---|
| BFS from every junction | O(n · (n + m)) | O(n²) bits for the reach table | TLE at n = 2 · 10^4 |
| Kosaraju | O(n + m) | O(n + m) (graph + reversed graph) | accepted, about 0.1 s for n = 10^5, m = 2 · 10^5 |
| Tarjan (practice 4) | O(n + m) | O(n + m), no reversed graph | accepted, one pass |
| every schedule | O(2^n · m) | O(m) | TLE at n = 40 |
| 2-SAT (implication graph + Kosaraju) | O(n + m) on 2n nodes and 2m arrows | O(n + m) | accepted, about 0.3 s for n = 10^5, m = 2 · 10^5 |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| BFS from every junction | Time Limit Exceeded |
n searches of O(n + m) each | Kosaraju |
| pass 2 by junction number | 1 / 1 2 3 4 5 6 (expected 3 zones) |
a bottom zone climbs into every zone above it | go through order from the end |
pass 2 on the original roads (g instead of rg) |
1 / 1 2 3 4 5 6 on the first sample |
the exits still lead out of the zone | DFS on the flipped roads |
pick the earlier zone (<) |
request 1 broken! |
the earlier literal can force its opposite | comp[x] > comp[x ^ 1] picks x |
only one arrow per request (not x → y only) |
request 4 broken! on 2 4 / 1 M 2 M / 1 M 2 E / 1 E 2 M / 1 E 2 E (expected IMPOSSIBLE) |
half the forcing is lost, so M and E never meet in one zone | add both x ^ 1 → y and y ^ 1 → x |
| recursive DFS on a 2 · 10^5-long road, C++ with an 8 MB stack | Segmentation fault |
2 · 10^5 nested calls | larger stack or iterative DFS |
| recursive DFS in Python | RecursionError: maximum recursion depth exceeded |
the default limit is 1000 frames | iterative DFS with an edge pointer |
| trying every schedule | Time Limit Exceeded |
2^n schedules | 2-SAT |
The "only one arrow" row was run on four requests that together forbid every schedule; the correct program prints IMPOSSIBLE on the same input, and on the first sample the one-arrow version prints request 2 broken!.
Mini project
Write a zone toolbox: kosaraju(n, edges) and tarjan(n, edges) that both return the zone of every junction, condense(n, edges, comp) that returns the condensation DAG without repeated arrows, and a TwoSat class with either(x, y), implies(x, y), exactlyOne(x, y), atMostOne(x, y) and solve(). Print the condensation of a random 30-junction city in Graphviz DOT format (one cluster per zone) and look at it. Stress test Kosaraju against Tarjan and against the BFS brute force, and TwoSat against trying every assignment, on thousands of tiny inputs. Finally time Kosaraju vs Tarjan, recursive vs iterative, for n = 10^5, 10^6.
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. Fewest new roads to make one zone. Same input as One-way Zones. Print the fewest new one-way roads that must be built so that the whole city becomes a single zone.
Solution
Build the condensation. A source zone (no road comes in) needs at least one new road coming in, and a sink zone (no road goes out) needs at least one new road going out; one new road can serve at most one source and one sink. So at least max(#sources, #sinks) roads are needed, and that many is always enough (link the sinks to the sources in a chain that closes into a loop, pairing them up carefully). The special case: if the city is already one zone, the answer is 0, not max(1, 1) = 1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) { // last finished first
int v = order[i];
if (!comp[v]) dfs2(v, ++c);
}
if (c == 1) { cout << 0 << "\n"; return 0; } // already one zone
vector<bool> hasIn(c + 1, false), hasOut(c + 1, false);
for (int a = 1; a <= n; a++)
for (int b : g[a])
if (comp[a] != comp[b]) hasOut[comp[a]] = hasIn[comp[b]] = true; // a road between two zones
int sources = 0, sinks = 0;
for (int z = 1; z <= c; z++) {
sources += !hasIn[z]; // no road comes in
sinks += !hasOut[z]; // no road goes out
}
cout << max(sources, sinks) << "\n";
}
The three samples of Z1: the chain A → B → C needs one road (1 → 4); three lonely junctions need a loop of three roads; the ring is already one zone.
1
3
0
2. Max coins on a one-way drive. Junction v holds coin_v coins (0 ≤ coin_v ≤ 10^9). You start at any junction, drive along one-way roads as long as you like (roads and junctions may be repeated), and collect the coins of every junction you visit, each junction only once. Print the maximum total. Input: n m, then coin_1 … coin_n, then the m roads.
Solution
Inside a zone you can visit every junction and come back, so entering a zone means collecting all of it: sum[z] is the zone's total. Between zones you can only move along the condensation DAG, so the answer is the heaviest path in the DAG: best[z] = sum[z] + max(best[w]) over arrows z → w. Kosaraju's zone numbers are already a topological order (arrows go to bigger numbers), so computing best from the last zone down to the first needs no extra sort. Totals reach 2 · 10^14: long long.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
vector<ll> coin(n + 1);
for (int v = 1; v <= n; v++) cin >> coin[v];
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) { // last finished first
int v = order[i];
if (!comp[v]) dfs2(v, ++c);
}
vector<ll> sum(c + 1, 0), best(c + 1, 0);
for (int v = 1; v <= n; v++) sum[comp[v]] += coin[v]; // a zone is collected whole
vector<vector<int>> zg(c + 1); // the condensation: one dot per zone
for (int a = 1; a <= n; a++)
for (int b : g[a])
if (comp[a] != comp[b]) zg[comp[a]].push_back(comp[b]);
ll ans = 0;
for (int z = c; z >= 1; z--) { // roads go to bigger numbers: do them first
best[z] = sum[z];
for (int w : zg[z]) best[z] = max(best[z], sum[z] + best[w]);
ans = max(ans, best[z]);
}
cout << ans << "\n";
}
The first sample city with coins 5 1 2 3 1 4 (zone A = 8, B = 3, C = 5, drive A → B → C), and 4 3 / 1 10 1 1 / 1 2 / 1 3 / 3 4 (1 → 2 collects 11, better than 1 → 3 → 4 with 3):
16
11
3. 2-SAT: "exactly one of a, b". Same input as Shift Requests, but each request now means exactly one of "a gets s" and "b gets t" must come true.
Solution
"Exactly one of x, y" is two clauses: (x or y), at least one, and (not x or not y), not both. Each clause is two arrows, so a request adds four. The self-check now tests that exactly one side holds.
#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<array<int, 2>> req(m);
auto lit = [](int v, char s) { return 2 * (v - 1) + (s == 'E'); }; // M: even, E: odd
for (auto &[x, y] : req) {
int a, b;
char s, t;
cin >> a >> s >> b >> t;
x = lit(a, s), y = lit(b, t); // EXACTLY one of: a gets s, b gets t
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
auto clause = [&](int x, int y) { // x OR y: two arrows
g[x ^ 1].push_back(y);
g[y ^ 1].push_back(x);
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
};
for (auto [x, y] : req) {
clause(x, y); // at least one
clause(x ^ 1, y ^ 1); // not both
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
bool hx = ans[x / 2] == "ME"[x & 1], hy = ans[y / 2] == "ME"[y & 1];
if (hx == hy) { // both or neither: broken
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
for (char ch : ans) cout << ch << " ";
}
3 2 / 1 M 2 M / 2 M 3 E, then 1 1 / 1 M 1 M (exactly one of x and x is impossible), then the Z2 sample read as "exactly one" (volunteer 1 cannot satisfy both "exactly one of 1M, 2M" and "exactly one of 1E, 2M"):
M E E
IMPOSSIBLE
IMPOSSIBLE
4. Tarjan's one-pass SCC. Find the zones of One-way Zones with a single DFS and no reversed graph.
Solution
Give every junction a visiting time tin, and keep low[v], the smallest tin that v's DFS subtree can reach through one road back into a junction that is still on the stack. Junctions are pushed on a stack when entered. When v finishes with low[v] == tin[v], nothing below v can climb above it, so v is the first junction of its zone, and everything above v on the stack is exactly that zone: pop it. Tarjan finds the zones in reverse topological order (sinks first), the opposite of Kosaraju. O(n + m), one pass, no rg.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, c = 0, timer = 0;
vector<vector<int>> g;
vector<int> tin, low, comp, st;
vector<bool> onStack;
void dfs(int v) {
tin[v] = low[v] = ++timer; // visiting time
st.push_back(v);
onStack[v] = true;
for (int u : g[v]) {
if (!tin[u]) { // tree edge
dfs(u);
low[v] = min(low[v], low[u]);
} else if (onStack[u]) // back into the open part of the stack
low[v] = min(low[v], tin[u]);
}
if (low[v] == tin[v]) { // v is the first junction of its zone
c++;
while (true) {
int u = st.back();
st.pop_back();
onStack[u] = false;
comp[u] = c;
if (u == v) break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b); // no flipped copy needed
}
tin.assign(n + 1, 0);
low.assign(n + 1, 0);
comp.assign(n + 1, 0);
onStack.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!tin[v]) dfs(v);
vector<vector<int>> zones(c + 1);
for (int v = 1; v <= n; v++) zones[comp[v]].push_back(v);
sort(zones.begin() + 1, zones.end()); // by smallest junction
cout << c << "\n";
for (int z = 1; z <= c; z++) {
for (int v : zones[z]) cout << v << " ";
cout << "\n";
}
}
The three samples of Z1, the same answers as Kosaraju:
3
1
2 3
4 5 6
3
1
2
3
1
1 2 3 4
Quick quiz
A request says: "volunteer 3 gets E, or volunteer 5 gets M". Which two arrows go into the implication graph?
g[x ^ 1].push_back(y);
g[y ^ 1].push_back(x);
A) 3E → 5M only · B) 3M → 5M and 5E → 3E · C) 3M → 5E and 5M → 3E · D) 5M → 3E only
Answer
B. x = "3 gets E", y = "5 gets M". If 3 doesn't get E (3M), 5 must get M: 3M → 5M. If 5 doesn't get M (5E), 3 must get E: 5E → 3E.
Interview questions
- What is a strongly connected component? A maximal set of vertices of a directed graph in which every vertex can reach every other one. The SCCs split the vertices into disjoint groups.
- Explain Kosaraju's algorithm and its complexity. DFS on the graph, recording vertices in finish order; then DFS on the reversed graph in reverse finish order, each DFS collecting one SCC. Two passes, O(n + m).
- Why must the second pass go in reverse finish order? The last finished vertex lies in a source SCC, which becomes a sink in the reversed graph, so a DFS from it cannot leave its SCC. In another order, a DFS can start in a sink SCC and climb into others on the reversed roads.
- What is the condensation, and why is it a DAG? One node per SCC and an edge for every edge between different SCCs. A cycle among SCCs would make them mutually reachable, so they would be one SCC.
- How is 2-SAT solved? Two nodes per variable, two implication edges per clause (¬a → b and ¬b → a), SCCs of that graph. Unsatisfiable iff some x and ¬x share an SCC; otherwise set x true when comp[x] comes later than comp[¬x] in topological order. O(n + m).
- Kosaraju vs Tarjan? Both O(n + m). Kosaraju is simpler to get right and needs the reversed graph; Tarjan is one pass with
tin/lowand a stack, uses less memory and produces SCCs in reverse topological order. - Why is 3-SAT not solved the same way? A clause of three literals does not turn into single "if one is false, then this one is true" implications, so there is no implication graph. 3-SAT is NP-complete; 2-SAT is linear.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Directed graph | Nodes joined by one-way edges a → b | the city of one-way roads |
| Edge / road | A one-way connection from a to b | 6 → 2 |
| Path | A sequence of edges, each starting where the last ended | 4 → 5 → 6 → 2 |
| Cycle | A path that returns to its start | 4 → 5 → 6 → 4 |
| Reachability | u reaches v if some path goes from u to v | 4 reaches 1, 1 reaches nobody |
| Strongly connected component (SCC) | A maximal group where everyone reaches everyone; a "zone" | {4, 5, 6} |
| BFS / DFS | Breadth-first / depth-first search over a graph | the brute force / Kosaraju |
| Finish order | The order in which a DFS completes vertices (all their edges explored) | 1 3 2 6 5 4 |
| Kosaraju's algorithm | DFS for the finish order, then DFS on the reversed graph in reverse finish order | Problem Z1 |
| Reversed (transposed) graph | The same graph with every edge flipped | rg[b].push_back(a) |
| Source component | An SCC with no edge coming in from another SCC | zone A |
| Sink component | An SCC with no edge going out to another SCC | zone C = {1} |
| Condensation | The graph with one node per SCC and edges between different SCCs | A → B → C |
| DAG | Directed acyclic graph: a directed graph with no cycle | every condensation |
| Topological order | An order of a DAG's nodes in which every edge goes forward | Kosaraju's zone numbers |
| Tarjan's algorithm | One-pass SCC algorithm with visiting times, low values and a stack | practice 4 |
Low value (low[v]) |
The smallest visiting time v's subtree can reach on the stack | low[v] == tin[v]: v starts a zone |
| Iterative DFS | DFS with an explicit stack and an edge pointer per vertex, no recursion | the Java and Python solutions |
| Recursion depth / stack overflow | Too many nested calls for the call stack | Segmentation fault, RecursionError |
| Adjacency list | For every node, the list of its outgoing edges | g[v] |
| Compressed adjacency (CSR) | All lists in one array, with a start index per node | the Java solutions |
| 2-SAT | Deciding whether clauses of two literals can all be true at once | Problem Z2 |
| Boolean variable | A yes/no unknown | "volunteer v gets E" |
| Literal | A variable or its negation | "3 gets E", "3 gets M" |
| Negation | The opposite literal; here x ^ 1 |
2 ↔ 3 = "2 gets M" ↔ "2 gets E" |
| Clause | Two literals joined by OR | "2 gets M or 1 gets M" |
| Implication | "If p then q", an arrow p → q | 1E → 2M |
| Implication graph | 2n literal nodes, two arrows per clause | the 2-SAT graph |
| Skew symmetry | p → q is an arrow exactly when ¬q → ¬p is | the two arrows of a clause |
| Satisfiable / IMPOSSIBLE | Some assignment keeps every clause / none does | M M E / IMPOSSIBLE |
| Bitmask | An integer whose bits encode choices | bit i: volunteer i + 1 gets E |
| Brute force | Trying every possibility | every schedule, BFS from everyone |
| Self-check | The program verifies its own answer before printing it | request 1 broken! |
| Stress test | Comparing a fast solution with a slow, surely-correct one on random inputs | all 500 tests passed |
| DP on a DAG | Computing a value per node from its successors in topological order | max coins, practice 2 |
| Time Limit Exceeded (TLE) / Wrong Answer (WA) | Too slow / wrong output | BFS from everyone: TLE; pass 2 by number: WA |
Summary
- A zone (SCC) is where everyone reaches everyone, both ways. A BFS from every junction is O(n(n + m)): TLE.
- Kosaraju: pass 1 writes each junction when it finishes; flip every road; pass 2 goes through the list from the end, one DFS per zone. O(n + m).
- The last finished junction lies in a source zone, a sink of the flipped graph, so the drive cannot leave it. Pass 2 by number prints
1zone instead of3. - Zones come out in topological order; the condensation is a DAG, ready for DP.
- 2-SAT: two nodes per variable, request "x or y" = arrows ¬x → y and ¬y → x. x and ¬x in one zone:
IMPOSSIBLE. Otherwise pick the literal whose zone comes later (comp[x] > comp[x ^ 1]). - A self-check turned the flipped comparison into
request 1 broken!instead of a silent WA.
Solutions in C++, Java and Python
Problem Z1 · One-way Zones
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> g, rg; // roads and flipped roads
vector<int> order, comp;
vector<bool> seen;
void dfs1(int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v); // finished: write it down
}
void dfs2(int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c); // flipped roads
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
g.assign(n + 1, {});
rg.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
rg[b].push_back(a);
}
seen.assign(n + 1, false);
for (int v = 1; v <= n; v++) if (!seen[v]) dfs1(v);
comp.assign(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) { // last finished first
int v = order[i];
if (!comp[v]) dfs2(v, ++c);
}
vector<vector<int>> zones(c + 1);
for (int v = 1; v <= n; v++) zones[comp[v]].push_back(v);
sort(zones.begin() + 1, zones.end()); // by smallest junction
cout << c << "\n";
for (int z = 1; z <= c; z++) {
for (int v : zones[z]) cout << v << " ";
cout << "\n";
}
}
Java (iterative DFS with an edge pointer, compressed adjacency arrays, byte-level input)
import java.io.*;
import java.util.*;
public class Main {
static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
static int nextInt() throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + (b - '0'); b = in.read(); }
return r;
}
public static void main(String[] args) throws IOException {
int n = nextInt(), m = nextInt();
int[] ea = new int[m], eb = new int[m];
int[] gs = new int[n + 2], rs = new int[n + 2]; // compressed adjacency lists
for (int i = 0; i < m; i++) {
ea[i] = nextInt(); eb[i] = nextInt();
gs[ea[i] + 1]++; rs[eb[i] + 1]++;
}
for (int v = 1; v <= n + 1; v++) { gs[v] += gs[v - 1]; rs[v] += rs[v - 1]; }
int[] g = new int[m], rg = new int[m], gp = gs.clone(), rp = rs.clone();
for (int i = 0; i < m; i++) { g[gp[ea[i]]++] = eb[i]; rg[rp[eb[i]]++] = ea[i]; }
// g[gs[v] .. gs[v+1]) are the roads out of v, rg the flipped roads
boolean[] seen = new boolean[n + 1];
int[] order = new int[n], it = new int[n + 1], stack = new int[n + 1];
int k = 0;
for (int s = 1; s <= n; s++) { // pass 1: iterative DFS, finish order
if (seen[s]) continue;
int sp = 0;
stack[sp++] = s; seen[s] = true; it[s] = gs[s];
while (sp > 0) {
int v = stack[sp - 1];
if (it[v] < gs[v + 1]) {
int u = g[it[v]++];
if (!seen[u]) { seen[u] = true; it[u] = gs[u]; stack[sp++] = u; }
} else {
sp--;
order[k++] = v; // finished: write it down
}
}
}
int[] comp = new int[n + 1];
int c = 0;
for (int i = n - 1; i >= 0; i--) { // pass 2: last finished first, flipped roads
int s = order[i];
if (comp[s] != 0) continue;
comp[s] = ++c;
int sp = 0;
stack[sp++] = s;
while (sp > 0) {
int v = stack[--sp];
for (int j = rs[v]; j < rs[v + 1]; j++)
if (comp[rg[j]] == 0) { comp[rg[j]] = c; stack[sp++] = rg[j]; }
}
}
int[] label = new int[c + 1]; // renumber zones by smallest junction
int z = 0;
for (int v = 1; v <= n; v++) if (label[comp[v]] == 0) label[comp[v]] = ++z;
StringBuilder[] zone = new StringBuilder[c + 1];
for (int i = 1; i <= c; i++) zone[i] = new StringBuilder();
for (int v = 1; v <= n; v++) zone[label[comp[v]]].append(v).append(' ');
StringBuilder out = new StringBuilder();
out.append(c).append('\n');
for (int i = 1; i <= c; i++) out.append(zone[i]).append('\n');
System.out.print(out);
}
}
3
1
2 3
4 5 6
3
1
2
3
1
1 2 3 4
Python (iterative DFS: no recursion limit to hit)
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(n + 1)]
rg = [[] for _ in range(n + 1)] # flipped roads
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
g[a].append(b)
rg[b].append(a)
seen = [False] * (n + 1)
it = [0] * (n + 1)
order = []
for s in range(1, n + 1): # pass 1: iterative DFS, finish order
if seen[s]:
continue
seen[s] = True
stack = [s]
while stack:
v = stack[-1]
if it[v] < len(g[v]):
u = g[v][it[v]]
it[v] += 1
if not seen[u]:
seen[u] = True
stack.append(u)
else:
stack.pop()
order.append(v) # finished: write it down
comp = [0] * (n + 1)
c = 0
for s in reversed(order): # pass 2: last finished first
if comp[s]:
continue
c += 1
comp[s] = c
stack = [s]
while stack:
v = stack.pop()
for u in rg[v]:
if not comp[u]:
comp[u] = c
stack.append(u)
label = [0] * (c + 1) # zones ordered by smallest junction
zones = []
for v in range(1, n + 1):
if not label[comp[v]]:
zones.append([])
label[comp[v]] = len(zones)
zones[label[comp[v]] - 1].append(v)
out = [str(c)] + ["".join(f"{v} " for v in z) for z in zones]
sys.stdout.write("\n".join(out) + "\n")
main()
3
1
2 3
4 5 6
3
1
2
3
1
1 2 3 4
Both were also run on a 2 · 10^5-junction one-way ring (2 · 10^5 nested DFS steps) and on 2 · 10^5 junctions with a 10^5-long road plus random roads; their output matched the C++ program exactly.
Problem Z2 · Shift Requests
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<array<int, 2>> req(m);
auto lit = [](int v, char s) { return 2 * (v - 1) + (s == 'E'); }; // M: even, E: odd
for (auto &[x, y] : req) {
int a, b;
char s, t;
cin >> a >> s >> b >> t;
x = lit(a, s), y = lit(b, t); // a gets s OR b gets t
}
int N = 2 * n; // a node for every "volunteer gets shift"
vector<vector<int>> g(N), rg(N);
for (auto [x, y] : req) { // x OR y:
g[x ^ 1].push_back(y); // not x → y
g[y ^ 1].push_back(x); // not y → x
rg[y].push_back(x ^ 1);
rg[x].push_back(y ^ 1);
}
vector<int> order, comp(N, 0);
vector<bool> seen(N, false);
function<void(int)> dfs1 = [&](int v) {
seen[v] = true;
for (int u : g[v]) if (!seen[u]) dfs1(u);
order.push_back(v);
};
function<void(int, int)> dfs2 = [&](int v, int c) {
comp[v] = c;
for (int u : rg[v]) if (!comp[u]) dfs2(u, c);
};
for (int v = 0; v < N; v++) if (!seen[v]) dfs1(v);
int c = 0;
for (int i = N - 1; i >= 0; i--) if (!comp[order[i]]) dfs2(order[i], ++c);
string ans;
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { cout << "IMPOSSIBLE\n"; return 0; }
ans += comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
auto [x, y] = req[k];
if (ans[x / 2] != "ME"[x & 1] && ans[y / 2] != "ME"[y & 1]) {
cout << "request " << k + 1 << " broken!\n";
return 0;
}
}
for (char ch : ans) cout << ch << " ";
}
Java (the arrows are stored in the same order as the C++ code, so it prints the same schedule)
import java.io.*;
import java.util.*;
public class Main {
static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
static int nextToken() throws IOException { // a number, or the letter M / E as a character code
int b = in.read();
while (b == ' ' || b == '\n' || b == '\r') b = in.read();
if (b == 'M' || b == 'E') return b;
int r = 0;
while (b >= '0' && b <= '9') { r = r * 10 + (b - '0'); b = in.read(); }
return r;
}
public static void main(String[] args) throws IOException {
int n = nextToken(), m = nextToken();
int[] rx = new int[m], ry = new int[m];
for (int k = 0; k < m; k++) {
int a = nextToken(), s = nextToken(), b = nextToken(), t = nextToken();
rx[k] = 2 * (a - 1) + (s == 'E' ? 1 : 0); // M: even, E: odd
ry[k] = 2 * (b - 1) + (t == 'E' ? 1 : 0); // rx OR ry
}
int N = 2 * n, E = 2 * m;
int[] from = new int[E], to = new int[E]; // arrows in the same order as the C++ code
for (int k = 0; k < m; k++) {
from[2 * k] = rx[k] ^ 1; to[2 * k] = ry[k]; // not x -> y
from[2 * k + 1] = ry[k] ^ 1; to[2 * k + 1] = rx[k]; // not y -> x
}
int[] gs = new int[N + 1], rs = new int[N + 1];
for (int e = 0; e < E; e++) { gs[from[e] + 1]++; rs[to[e] + 1]++; }
for (int v = 1; v <= N; v++) { gs[v] += gs[v - 1]; rs[v] += rs[v - 1]; }
int[] g = new int[E], rg = new int[E], gp = gs.clone(), rp = rs.clone();
for (int e = 0; e < E; e++) { g[gp[from[e]]++] = to[e]; rg[rp[to[e]]++] = from[e]; }
boolean[] seen = new boolean[N];
int[] order = new int[N], it = new int[N], stack = new int[N];
int cnt = 0;
for (int s = 0; s < N; s++) { // pass 1: iterative DFS
if (seen[s]) continue;
int sp = 0;
stack[sp++] = s; seen[s] = true; it[s] = gs[s];
while (sp > 0) {
int v = stack[sp - 1];
if (it[v] < gs[v + 1]) {
int u = g[it[v]++];
if (!seen[u]) { seen[u] = true; it[u] = gs[u]; stack[sp++] = u; }
} else { sp--; order[cnt++] = v; }
}
}
int[] comp = new int[N];
int c = 0;
for (int i = N - 1; i >= 0; i--) { // pass 2 on the flipped arrows
int s = order[i];
if (comp[s] != 0) continue;
comp[s] = ++c;
int sp = 0;
stack[sp++] = s;
while (sp > 0) {
int v = stack[--sp];
for (int j = rs[v]; j < rs[v + 1]; j++)
if (comp[rg[j]] == 0) { comp[rg[j]] = c; stack[sp++] = rg[j]; }
}
}
char[] ans = new char[n];
for (int i = 0; i < n; i++) {
if (comp[2 * i] == comp[2 * i + 1]) { System.out.println("IMPOSSIBLE"); return; }
ans[i] = comp[2 * i] > comp[2 * i + 1] ? 'M' : 'E'; // the later zone wins
}
for (int k = 0; k < m; k++) { // self-check every request
boolean hx = ans[rx[k] / 2] == "ME".charAt(rx[k] & 1);
boolean hy = ans[ry[k] / 2] == "ME".charAt(ry[k] & 1);
if (!hx && !hy) { System.out.println("request " + (k + 1) + " broken!"); return; }
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < n; i++) out.append(ans[i]).append(i + 1 < n ? " " : "\n");
System.out.print(out);
}
}
M M E
IMPOSSIBLE
E M
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
req = []
for i in range(m):
a, s, b, t = data[2 + 4 * i: 6 + 4 * i]
x = 2 * (int(a) - 1) + (s == b"E") # M: even, E: odd
y = 2 * (int(b) - 1) + (t == b"E")
req.append((x, y)) # x OR y
N = 2 * n
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for x, y in req:
g[x ^ 1].append(y) # not x -> y
g[y ^ 1].append(x) # not y -> x
rg[y].append(x ^ 1)
rg[x].append(y ^ 1)
seen = [False] * N
it = [0] * N
order = []
for s in range(N): # pass 1: iterative DFS
if seen[s]:
continue
seen[s] = True
stack = [s]
while stack:
v = stack[-1]
if it[v] < len(g[v]):
u = g[v][it[v]]
it[v] += 1
if not seen[u]:
seen[u] = True
stack.append(u)
else:
stack.pop()
order.append(v)
comp = [0] * N
c = 0
for s in reversed(order): # pass 2 on the flipped arrows
if comp[s]:
continue
c += 1
comp[s] = c
stack = [s]
while stack:
v = stack.pop()
for u in rg[v]:
if not comp[u]:
comp[u] = c
stack.append(u)
ans = []
for i in range(n):
if comp[2 * i] == comp[2 * i + 1]:
print("IMPOSSIBLE")
return
ans.append("M" if comp[2 * i] > comp[2 * i + 1] else "E") # the later zone wins
for k, (x, y) in enumerate(req): # self-check every request
if ans[x // 2] != "ME"[x & 1] and ans[y // 2] != "ME"[y & 1]:
print(f"request {k + 1} broken!")
return
print(" ".join(ans))
main()
M M E
IMPOSSIBLE
E M
Both were also run on a solvable instance with 10^5 volunteers and 2 · 10^5 requests (including a 10^5-long chain of forced choices): the schedules matched the C++ program's, in about 1.1 s for Python.