Why this matters when you build with AI
Ask an AI tool whether a directed graph is strongly connected and you often get one depth-first search (DFS) from vertex 0, followed by a check that every vertex was visited. That tells you that vertex 0 can reach everything. It does not tell you that everything can reach vertex 0. A one-way street from 1 to 0 with no way back passes that check, and the answer is wrong. Ask for "the number of extra edges needed" and you may get the number of components minus one. That is wrong too. A chain of three components needs one extra edge, but five isolated vertices need five.
You catch these in a few minutes. Test a single directed edge from 0 to 1, which is not strongly connected. Test a chain of three components, which needs one extra edge. Test five isolated vertices, which need five. The lesson gives you the method and the tests.
A prompt that states the requirements:
Write a C++17 function that takes a directed graph with n vertices and m edges (self-loops
and repeated edges allowed). Return the strongly connected components with an iterative
method, so that a path of 300000 vertices does not overflow the stack. Build the condensation
DAG, and return the smallest number of new directed edges that make the whole graph strongly
connected. Explain in one sentence why the answer is 0 when there is one component.A good answer uses an explicit stack, builds the condensation with one node per component, and does not claim a single search is enough. Check each of these in the code. Then run the checks in "Check them against each other".
Terms used
- A directed graph has edges with a direction. The edge
u -> vlets you walk from u to v, and not back. - A vertex v can reach w if there is a directed walk from v to w.
- A strongly connected component (SCC) is a largest group of vertices where every vertex can reach every other one. A single vertex with no cycle is an SCC by itself.
- A graph is strongly connected if it has exactly one SCC.
- The condensation is the graph you get by shrinking each SCC to one node. The result has no cycles, so it is a directed acyclic graph (DAG).
- A topological order of a DAG lists its nodes so that every edge goes from an earlier node to a later one.
- A source in a DAG is a node with no incoming edges. A sink is a node with no outgoing edges.
- A back edge in a DFS goes from a vertex to one of its ancestors that is still on the DFS path.
- The lowlink of v in Tarjan's method is the smallest entry time that v can reach through its subtree and back edges, where the back edges point to vertices that are still on the stack.
- A "block" in this lesson means one SCC, which is a node of the condensation.
The idea: groups that loop back
Take a small example first. Vertices 0, 1 and 2 form a directed cycle 0 -> 1 -> 2 -> 0. There is also an edge 2 -> 3, and nothing leaves vertex 3. The graph has two SCCs: {0, 1, 2} and {3}.
A test for "one SCC" needs two searches. Search from vertex 0 along the edges, and search from vertex 0 along the reversed edges (every edge turned around). If both searches reach all vertices, every vertex can reach 0 and 0 can reach every vertex, so the graph is one SCC. In the example, the first search reaches 0, 1, 2 and 3. The reversed search reaches only 0, 1 and 2, because 3 has no edge back. The graph is not one SCC, as expected.
That test only answers yes or no. To list the SCCs we need Tarjan's method, which was described by Robert Tarjan in "Depth-first search and linear graph algorithms", SIAM Journal on Computing, volume 1, issue 2, pages 146 to 160, 1972. It runs one DFS. Each vertex gets an entry time idx, and a lowlink low. Vertices stay on a stack while they are being explored. When a vertex finishes with low[v] == idx[v], it is the root of an SCC, and every vertex above it on the stack belongs to that SCC.
A trace on the example
Run the example through Tarjan with vertex 0 first. The entry times are idx[0] = 0, idx[1] = 1, idx[2] = 2 and idx[3] = 3. From 2, the edge back to 0 finds 0 on the stack, so low[2] becomes 0. Vertex 3 has no outgoing edges, so it finishes first with low[3] = idx[3] = 3. It forms an SCC by itself and is popped from the stack. Then 2 finishes with low[2] = 0, which is not equal to idx[2] = 2, so it is not a root. Its parent 1 and then 0 finish. Vertex 0 has low[0] = idx[0] = 0, so it is the root, and the stack holds 2, 1 and 0 above it. They are popped as one SCC.
The program confirms this order. On the input 4 4 / 0 1 / 1 2 / 2 0 / 2 3, the output is:
components: 2
block 0: 3
block 1: 0 1 2
condensation edges: 1->0
new streets needed: 1
longest chain of junctions: 4 via blocks 1 0Block 0 is {3}, which finished first, and block 1 is {0, 1, 2}. Tarjan numbers components in the order they finish. An SCC finishes only after every SCC it can reach has finished. So if there is an edge from one component to another, the first one has the larger number. The numbers run in reverse topological order.
The condensation and its order
Shrink each SCC to one node and keep one edge for each pair of components that has at least one edge between them. The result, the condensation, is a DAG. In the example it has two nodes and one edge, from the {0, 1, 2} block to the {3} block.
A DAG always has a topological order. One easy way to find it is Kahn's algorithm: repeatedly take a node with no incoming edges, output it, and remove its outgoing edges. A later section uses this order to run a DP. The code in the lesson builds the order this way.
Kosaraju's method gives the order directly. It was suggested by S. Rao Kosaraju in 1978 without being published, and it was published by Micha Sharir in "A strong-connectivity algorithm and its applications in data flow analysis", Computers & Mathematics with Applications, volume 7, issue 1, pages 67 to 72, 1981. It works in two passes. The first pass runs a DFS on the graph and records the finish order. The second pass goes through the vertices in reverse finish order and runs a search on the reversed graph. Each search finds exactly one SCC. The components come out in topological order, the opposite of Tarjan's numbering.
Both methods are linear time. This lesson gives Tarjan's method in full and Kosaraju's in the same header. The stress test checks that they give the same partition and that each one's numbering follows the rules above.
Counting the streets needed
Take a city where every street is one way. Some junctions may be unreachable from others. How many new one-way streets make the whole city strongly connected, so that every junction can reach every other one?
If the condensation has one node, the answer is 0. Otherwise, count two numbers over the condensation: the number of sources (blocks with no incoming streets from other blocks) and the number of sinks (blocks with no outgoing streets to other blocks). The answer is the larger of the two.
Check it on three cases. A chain of three blocks A -> B -> C has one source (A) and one sink (C), so the answer is 1: add a street from C back to A. Five isolated vertices have five sources and five sinks, so the answer is 5. A directed cycle needs five streets for five vertices, and a graph with four new streets and five vertices cannot give every vertex both an incoming and an outgoing street. The third case is a single cycle, which is already one SCC, so the answer is 0.
This is a known result for this problem. K. P. Eswaran and R. E. Tarjan introduced the problem in "Augmentation problems", SIAM Journal on Computing, volume 5, issue 4, pages 653 to 665, 1976. A later note by S. Raghavan reports an error in the 1976 construction for the edges themselves (as summarised on the Wikipedia article "Strong connectivity augmentation"). This lesson does not use that construction. It gives the count only, and checks the count against a brute force search on small graphs.
Worked example: one-way streets
A town has nine junctions, numbered 0 to 8. The file example.txt lists each one-way street as u v, from junction u to junction v:
9 12
0 1
1 2
2 0
2 3
3 4
4 5
5 3
5 6
6 7
7 6
8 0
0 6The task: how many new one-way streets make the town strongly connected? And what is the longest route through blocks of junctions, where each block is counted once and each step follows a one-way street?
Work it by hand first. The streets 0 -> 1 -> 2 -> 0 form a loop, so junctions 0, 1 and 2 are one block. The streets 3 -> 4 -> 5 -> 3 form a second block. Junctions 6 and 7 are a third block, because 6 -> 7 -> 6. Junction 8 has no incoming streets, so it is a block by itself. The streets between blocks are: {0,1,2} to {3,4,5} (through 2 to 3), {3,4,5} to {6,7} (through 5 to 6), {0,1,2} to {6,7} (through 0 to 6), and {8} to {0,1,2} (through 8 to 0).
The sources are the block {8}, which has no incoming streets. The only sink is {6,7}. So the answer is 1: add one street from 6 or 7 to 8. For the longest route, the chain {8}, {0,1,2}, {3,4,5}, {6,7} has 1 + 3 + 3 + 2 = 9 junctions, and no other route is longer.
Real output of the program:
components: 4
block 0: 6 7
block 1: 3 4 5
block 2: 0 1 2
block 3: 8
condensation edges: 1->0 2->0 2->1 3->2
new streets needed: 1
longest chain of junctions: 9 via blocks 3 2 1 0The block numbers come from Tarjan's method. Block 0 finished first and is the sink, so the chain reads from block 3 down to block 0.
The C++17 code
The header is scc.hpp. It holds the graph type, Tarjan's method, Kosaraju's method, the condensation, the street count and the longest-chain DP. Every search is iterative. Tarjan and Kosaraju both take O(n + m) time.
// scc.hpp: strongly connected components (Tarjan and Kosaraju, both iterative), the condensation,
// the number of new edges needed to make a digraph strongly connected, and a longest-chain DP.
#pragma once
#include <algorithm>
#include <queue>
#include <vector>
struct Digraph {
int n = 0;
std::vector<std::vector<int>> adj, radj; // out-neighbours and in-neighbours
explicit Digraph(int n_) : n(n_), adj(n_), radj(n_) {}
void add_edge(int u, int v) {
adj[u].push_back(v);
radj[v].push_back(u);
}
};
struct SccResult {
int count = 0; // number of components
std::vector<int> comp; // vertex -> component id
};
// Tarjan. Components are numbered in the order they are completed. A component is completed only
// after every component it can reach, so an edge u -> v between different components always has
// comp[u] > comp[v]. The numbers run in reverse topological order.
SccResult tarjan(const Digraph& g) {
int n = g.n;
SccResult r;
r.comp.assign(n, -1);
std::vector<int> idx(n, -1), low(n, 0), stk;
std::vector<char> on(n, 0);
struct Frame { int v; int it; };
std::vector<Frame> call;
int timer = 0;
for (int s = 0; s < n; s++) {
if (idx[s] != -1) continue;
idx[s] = low[s] = timer++;
stk.push_back(s);
on[s] = 1;
call.push_back({s, 0});
while (!call.empty()) {
int v = call.back().v;
if (call.back().it < (int)g.adj[v].size()) {
int to = g.adj[v][call.back().it++];
if (idx[to] == -1) {
idx[to] = low[to] = timer++;
stk.push_back(to);
on[to] = 1;
call.push_back({to, 0}); // no reference to call.back() is used after this push
} else if (on[to]) {
low[v] = std::min(low[v], idx[to]);
}
} else {
call.pop_back();
if (low[v] == idx[v]) {
int c = r.count++;
int w;
do {
w = stk.back();
stk.pop_back();
on[w] = 0;
r.comp[w] = c;
} while (w != v);
}
if (!call.empty()) {
int p = call.back().v;
low[p] = std::min(low[p], low[v]);
}
}
}
}
return r;
}
// Kosaraju. Pass 1: finish order on g. Pass 2: walk the reverse graph in reverse finish order.
// Components are numbered in topological order: an edge u -> v between components has comp[u] < comp[v].
SccResult kosaraju(const Digraph& g) {
int n = g.n;
SccResult r;
r.comp.assign(n, -1);
std::vector<int> order;
std::vector<char> seen(n, 0);
struct Frame { int v; int it; };
std::vector<Frame> call;
for (int s = 0; s < n; s++) {
if (seen[s]) continue;
seen[s] = 1;
call.push_back({s, 0});
while (!call.empty()) {
int v = call.back().v;
if (call.back().it < (int)g.adj[v].size()) {
int to = g.adj[v][call.back().it++];
if (!seen[to]) {
seen[to] = 1;
call.push_back({to, 0});
}
} else {
order.push_back(v); // v is finished
call.pop_back();
}
}
}
std::vector<int> st;
for (int i = n - 1; i >= 0; i--) {
int s = order[i];
if (r.comp[s] != -1) continue;
int c = r.count++;
r.comp[s] = c;
st.push_back(s);
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int to : g.radj[v]) {
if (r.comp[to] != -1) continue;
r.comp[to] = c;
st.push_back(to);
}
}
}
return r;
}
// The condensation: one node per component, one edge per pair of components that has an edge.
std::vector<std::vector<int>> condensation(const Digraph& g, const SccResult& s) {
std::vector<std::vector<int>> cadj(s.count);
for (int u = 0; u < g.n; u++)
for (int v : g.adj[u])
if (s.comp[u] != s.comp[v]) cadj[s.comp[u]].push_back(s.comp[v]);
for (auto& row : cadj) {
std::sort(row.begin(), row.end());
row.erase(std::unique(row.begin(), row.end()), row.end());
}
return cadj;
}
// Smallest number of new directed edges that make the graph strongly connected.
// If the graph has one component, the answer is 0. Otherwise it is max(sources, sinks), where a
// source is a component with no incoming edge and a sink is a component with no outgoing edge.
// (The brute force in stress.cpp confirms this on small graphs. The formula is the known result;
// this code does not give the edges themselves.)
int min_new_edges(int count, const std::vector<std::vector<int>>& cadj) {
if (count <= 1) return 0;
std::vector<char> has_in(count, 0), has_out(count, 0);
for (int c = 0; c < count; c++)
for (int d : cadj[c]) {
has_out[c] = 1;
has_in[d] = 1;
}
int sources = 0, sinks = 0;
for (int c = 0; c < count; c++) {
if (!has_in[c]) sources++;
if (!has_out[c]) sinks++;
}
return std::max(sources, sinks);
}
// Longest chain of components along the condensation, where a component counts its weight once.
// Returns the total weight and the chain, first component to last. Kahn's algorithm gives the order.
std::pair<long long, std::vector<int>> longest_chain(int count, const std::vector<std::vector<int>>& cadj,
const std::vector<long long>& weight) {
std::vector<int> indeg(count, 0), topo;
for (int c = 0; c < count; c++)
for (int d : cadj[c]) indeg[d]++;
std::queue<int> q;
for (int c = 0; c < count; c++)
if (indeg[c] == 0) q.push(c);
while (!q.empty()) {
int c = q.front();
q.pop();
topo.push_back(c);
for (int d : cadj[c])
if (--indeg[d] == 0) q.push(d);
}
if (count == 0) return {0, {}};
std::vector<long long> best(count);
std::vector<int> from(count, -1);
for (int c = 0; c < count; c++) best[c] = weight[c];
for (int c : topo)
for (int d : cadj[c])
if (best[c] + weight[d] > best[d]) {
best[d] = best[c] + weight[d];
from[d] = c;
}
int end = 0;
for (int c = 0; c < count; c++)
if (best[c] > best[end]) end = c;
std::vector<int> chain;
for (int c = end; c != -1; c = from[c]) chain.push_back(c);
std::reverse(chain.begin(), chain.end());
return {count == 0 ? 0 : best[end], chain};
}The demo program reads a graph, prints the blocks, the condensation, the street count and the longest chain. It is demo.cpp:
// demo.cpp: reads "n m" then m lines "u v" (one-way street from u to v). Prints the components,
// the condensation, the number of new streets needed, and the longest chain of blocks.
#include <cstdio>
#include "scc.hpp"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 1;
Digraph g(n);
for (int i = 0; i < m; i++) {
int u, v;
if (scanf("%d %d", &u, &v) != 2) return 1;
g.add_edge(u, v);
}
SccResult t = tarjan(g);
std::vector<std::vector<int>> members(t.count);
for (int v = 0; v < n; v++) members[t.comp[v]].push_back(v);
printf("components: %d\n", t.count);
for (int c = 0; c < t.count; c++) {
printf("block %d:", c);
for (int v : members[c]) printf(" %d", v);
printf("\n");
}
auto cadj = condensation(g, t);
printf("condensation edges:");
for (int c = 0; c < t.count; c++)
for (int d : cadj[c]) printf(" %d->%d", c, d);
printf("\n");
printf("new streets needed: %d\n", min_new_edges(t.count, cadj));
std::vector<long long> weight(t.count);
for (int c = 0; c < t.count; c++) weight[c] = (long long)members[c].size();
auto [total, chain] = longest_chain(t.count, cadj, weight);
printf("longest chain of junctions: %lld via blocks", total);
for (int c : chain) printf(" %d", c);
printf("\n");
return 0;
}Compile and run it with:
g++ -O2 -std=c++17 -Wall -Wextra -o demo demo.cpp && ./demo < example.txtThe longest-chain DP
The DP is the part that makes the condensation useful. Let best[c] be the largest total weight of a chain that ends at block c. A block with no incoming edges starts with its own weight. For each block c in topological order, look at each edge c -> d and set best[d] to best[c] + weight[d] if that is larger. Because the order is topological, best[c] is final before c is used, so one pass is enough. The answer is the largest best value, and the chain is found by remembering the block that set each value.
The order matters. If the code processed block d before block c, best[d] would be computed from an incomplete value, and the answer could be too small on some inputs. The stress test in "Check them against each other" compares the DP with a memoised recursion, which does not depend on the order.
Complexity
Tarjan and Kosaraju each visit every vertex once and every edge a constant number of times, so both take O(n + m) time and O(n + m) memory. The condensation and the DP are also O(n + m). The brute force used for checking takes time that grows very fast with the number of vertices, so it is only used for n up to 5. The time figures are bounds from the method. I did not time the programs on large graphs, so check the speed on your machine.
Check them against each other
The stress program stress.cpp makes random directed graphs with 1 to 6 vertices and up to 12 edges. Self-loops and repeated edges are allowed. For each graph it checks the following:
- Tarjan and Kosaraju each give the same partition as Floyd-Warshall reachability: two vertices share a component exactly when each can reach the other.
- Every edge between two components goes in the order that the numbering promises. In Tarjan,
comp[u] > comp[v]. In Kosaraju,comp[u] < comp[v]. - For graphs with up to 5 vertices, the street count from
min_new_edgesequals the smallest number of new edges found by searching all sets of new edges and testing strong connectivity. - The longest-chain value equals a memoised recursion on the condensation, and the chain returned is a real path with the right total.
Real output:
ok seed=1 tests=5000 brute_checked=4169 multi_component_graphs=3312 nonzero_answers=3312
ok seed=2024 tests=5000 brute_checked=4142 multi_component_graphs=3319 nonzero_answers=3319
ok seed=77 tests=8000 brute_checked=6638 multi_component_graphs=5298 nonzero_answers=5298About two thirds of the random graphs had more than one component, so the counting rule was tested on many cases.
To check that the stress test can catch a wrong count, one wrong variant was made by changing the last line of min_new_edges to return only the number of sources. It was run through the same stress test with seed 1, and it failed:
FAIL min_new test=4 brute=2 fast=1In that case the graph had two sinks and one source, so the answer is 2, and the variant printed 1. A number that only counts one side of the condensation misses the other side.
Common mistakes
Mistake 1: one search from vertex 0. A program that makes this mistake says "strongly connected" for 2 1 / 0 1. The search from 0 reaches vertex 1, but vertex 1 cannot get back to 0. Fix: use Tarjan or Kosaraju, or two searches (forward and reversed) from the same start.
Mistake 2: the components-minus-one count. For five isolated vertices the correct answer is 5. A program that prints components - 1 gives 4, and a cycle of four new streets leaves at least one vertex with no outgoing street. Fix: count sources and sinks of the condensation.
Mistake 3: a recursive DFS on a long chain. Symptom: a segmentation fault on a path of many vertices, with small inputs passing. I did not reproduce the crash in this lesson, because the depth that causes it depends on the stack limit (ulimit -s shows yours). Fix: use the explicit call stack, as in the header.
Mistake 4: a lowlink update from a finished component. In Tarjan, the lowlink update from a back edge only uses vertices still on the stack. If the code updates from every visited vertex, a vertex can be joined to a component it does not belong to. I checked this with a copy of the header where the on[to] test was removed. The stress test caught it on the random graphs with seed 1: FAIL partition test=4 pair=2,3, which means two vertices were put in one component although they cannot reach each other. The on[to] test in the header prevents this.
Mistake 5: a DP in the wrong order. Processing blocks in the order of their numbers without checking the direction of the numbering gives wrong answers when the numbering is the wrong way round. Tarjan numbers in reverse topological order and Kosaraju in topological order. Fix: use Kahn's order, as the header does, or check the numbering against the edges before you rely on it.
Mistake 6: counting edges inside a component. The condensation keeps only edges between different components. An edge inside a block does not help make the graph strongly connected, and counting it inflates the answer.
Checklist
- For "is it strongly connected", use an SCC method. One search from one vertex is not enough.
- Run the search with an explicit stack for large inputs.
- Update the lowlink only from vertices still on the stack (Tarjan).
- Build the condensation with one edge per pair of components, and remove duplicates.
- Count sources and sinks of the condensation, and answer
max(sources, sinks)when there is more than one component. - Compute the DP in topological order, and check the direction of your numbering against the edges.
- Test a single directed edge, a chain of three, five isolated vertices and a single cycle.
- Compare with a brute force on small random graphs before you trust the code.
What was checked
- All C++ code compiled with g++ 15.2.0 (Ubuntu) using
-O2 -std=c++17 -Wall -Wextra, with no warnings. stresspassed on 5000 graphs with seed 1, 5000 with seed 2024, and 8000 with seed 77. The graphs have 1 to 6 vertices, up to 12 edges, and may have self-loops and repeated edges. Reachability is checked with Floyd-Warshall, and the street count is checked against a search over all sets of new edges for graphs with up to 5 vertices.- The wrong variant that counts only sources failed the same stress test, as shown.
- The outputs in this lesson were copied from the program runs, including the tiny example used in "The idea" and the practice inputs.
- I did not time the code on large graphs, and I did not run a recursive version to show its crash point.
- Citations were checked in search results. Tarjan (1972) is "Depth-first search and linear graph algorithms", SIAM Journal on Computing, volume 1, issue 2, pages 146 to 160. Sharir (1981) is in Computers & Mathematics with Applications, volume 7, issue 1, pages 67 to 72. Eswaran and Tarjan (1976) is "Augmentation problems", SIAM Journal on Computing, volume 5, issue 4, pages 653 to 665. The note about the error in the 1976 construction is from the Wikipedia summary. I did not read the full texts of these papers.
- The Kosaraju credit to a 1978 unpublished suggestion is taken from the same search summary and is not checked against the original.
Summary
Tarjan's method finds the strongly connected components in one DFS, using entry times, lowlinks and a stack. Shrinking the components gives a DAG, and its topological order lets you run a DP for the longest chain. The number of one-way streets needed to make a graph strongly connected is the larger of the number of sources and the number of sinks of the condensation, unless there is only one component. The brute force agrees with this count on small graphs, and the wrong variant that counts only sources fails it.
Practice
Problem 1: find the sink and its number
In the example in example.txt, which block is the only sink, and what number does Tarjan give it?
Show the answer
Hint: a sink has no outgoing streets to other blocks. Look at the condensation edges.
Answer: the sink is block 0, which is the set {6, 7}. The condensation edges are 1->0, 2->0, 2->1 and 3->2. Block 0 appears only as a destination, so it has no outgoing edge. The program printed block 0: 6 7.
Problem 2: add one street
Take the example and add the street 6 -> 0. The file now has 13 streets. How many new streets are needed, and why?
Show the answer
Hint: the new street joins the block {6, 7} back into the big block. Which blocks are left?
Answer: one new street. Adding 6 -> 0 makes {0, ..., 7} one block, because 0 reaches 6 and 6 now reaches 0. Junction 8 is still separate. It has a street into the big block but none back. The output is:
components: 2
block 0: 0 1 2 3 4 5 6 7
block 1: 8
condensation edges: 1->0
new streets needed: 1
longest chain of junctions: 9 via blocks 1 0The block {8} is the only source and the big block is the only sink, so one street from the big block to 8 closes the gap.
Problem 3: why five and not four
Five junctions have no streets at all. Give the answer and a reason that does not depend on the formula.
Show the answer
Hint: think about how many incoming and outgoing streets each junction needs.
Answer: 5. In a strongly connected graph, every junction needs at least one outgoing street, because it must reach the others, and at least one incoming street, because the others must reach it. With five junctions, that means at least five streets in total, and five streets can form a single cycle. Four streets cannot give all five junctions an outgoing street. The program printed new streets needed: 5 on the input 5 0.
Problem 4: remove a street and check the chain
Take the example and remove the street 0 -> 6. Does the longest chain of junctions change? Predict the answer, then run the program.
Show the answer
Hint: the chain {8}, {0,1,2}, {3,4,5}, {6,7} does not use the street 0 -> 6.
Answer: no. The longest chain is still 9. The chain goes through the blocks {8}, {0,1,2}, {3,4,5} and {6,7}, using the streets 8 -> 0, 2 -> 3 and 5 -> 6. The street 0 -> 6 was a shortcut that gave a shorter route from {0,1,2} to {6,7}, not a longer one. The output for the input without it is:
components: 4
block 0: 6 7
block 1: 3 4 5
block 2: 0 1 2
block 3: 8
condensation edges: 1->0 2->1 3->2
new streets needed: 1
longest chain of junctions: 9 via blocks 3 2 1 0Problem 5: explain the topological order
Why does the DP need a topological order and not just any order of the blocks? Give a small example where processing blocks in the wrong order gives a wrong answer.
Show the answer
Hint: think of the chain A -> B -> C and of the value best[B] when you process B before A.
Answer: the value best[d] must be final before the code uses it to update the blocks after d. Worked by hand, not run: in a chain A -> B -> C with weights 1, 3 and 2, processing B before A sets best[B] = 3 and then best[C] = 5 from it. When A is processed later it raises best[B] to 4, which is too late to pass on to C. The answer 5 is then too small, because the true longest chain is 1 + 3 + 2 = 6. A topological order processes A first, so every value is final before it is used.