algo-graph-01
0.000
Challenge · difficulty 4/5
# Treasure runs on a directed road map
An adventurer roams a network of `n` outposts connected by **one-way** roads.
Outpost `i` holds `treasure[i]` gold (a **non-negative** integer). Starting at
outpost `start`, the adventurer may follow roads for as long as they like — even
driving around in circles — and **loots each outpost the first time they visit
it** (revisiting an already-looted outpost yields nothing).
Compute the **maximum total gold** the adventurer can collect.
Implement a file **`solution.py`** with:
```python
def max_treasure(n: int, treasure: Sequence[int],
roads: Sequence[Tuple[int, int]], start: int) -> int:
...
```
## Input
- `n` — number of outposts, labeled `0 .. n-1` (`1 <= n`).
- `treasure` — a list of `n` non-negative integers; `treasure[i]` is the gold at outpost `i`.
- `roads` — a list of directed edges `(u, v)` meaning there is a one-way road **from `u` to `v`**.
Roads may include **self-loops** `(u, u)` and **duplicate** edges.
- `start` — the outpost the adventurer begins at (`0 <= start < n`).
## Output
Return a single integer: the maximum gold collectible on any walk that begins at
`start`, counting each outpost's gold **at most once**.
## What "collect" means
Because roads are one-way, a walk visits a sequence of outposts and loots the
distinct ones it touches. Two consequences drive the problem:
- If a set of outposts is **mutually reachable** (you can get from any one to any
other and back — a strongly connected group), then once you enter the group you
can tour **all** of its outposts, so their gold is collected together.
- Once you leave such a group along a road, you can never return to it (otherwise
it would have been part of the group). So the walk, viewed at the level of these
groups, moves **strictly forward** through the road network.
Gold is never negative, so lingering to loot more is never harmful; the only real
decision is **which forward branch to commit to**.
## Examples
```python
# 0 -> 1 -> 2, values 1,10,100
assert max_treasure(3, [1, 10, 100], [(0, 1), (1, 2)], 0) == 111
assert max_treasure(3, [1, 10, 100], [(0, 1), (1, 2)], 2) == 100
# 0 <-> 1 is one mutually-reachable group: loot both from either start
assert max_treasure(2, [3, 4], [(0, 1), (1, 0)], 0) == 7
# unreachable fortune is excluded
assert max_treasure(3, [1, 1, 1000], [(0, 1)], 0) == 2
# {0,1,2} form a cycle (1+2+3), then 2 -> 3 worth 100
assert max_treasure(4, [1, 2, 3, 100], [(0, 1), (1, 2), (2, 0), (2, 3)], 0) == 106
# a shared downstream outpost is counted once, not twice
# 0->1->3 and 0->2->3
assert max_treasure(4, [1, 10, 20, 100], [(0, 1), (0, 2), (1, 3), (2, 3)], 0) == 121
# you must pick the richer of two mutually-exclusive branches
assert max_treasure(3, [1, 5, 50], [(0, 1), (0, 2)], 0) == 51
```
## Constraints & notes
- Only outposts **reachable from `start`** can ever be looted.
- Self-loops and duplicate roads must be handled gracefully.
- The graph can be **large and deep**: expect up to about `10^5` outposts and
`2 * 10^5` roads, including a single chain that long. A solution whose recursion
depth grows with the graph will overflow — use an **iterative** approach. An
overall `O(n + m)` algorithm is expected.tests/test_treasure.py
import random
from solution import max_treasure
# --------------------------------------------------------------------------
# Independent reference: O(n^3) transitive-closure SCCs + recursive DAG DP.
# Deliberately a different algorithm than the solution (no Kosaraju/Tarjan).
# Only used on small graphs.
# --------------------------------------------------------------------------
def _brute(n, treasure, roads, start):
adj = [[] for _ in range(n)]
for u, v in roads:
adj[u].append(v)
reach = [[False] * n for _ in range(n)]
for s in range(n):
seen = {s}
stack = [s]
while stack:
x = stack.pop()
for y in adj[x]:
if y not in seen:
seen.add(y)
stack.append(y)
for y in seen:
reach[s][y] = True
reach[s][s] = True
comp = [-1] * n
cid = 0
for i in range(n):
if comp[i] != -1:
continue
comp[i] = cid
for j in range(n):
if comp[j] == -1 and reach[i][j] and reach[j][i]:
comp[j] = cid
cid += 1
cw = [0] * cid
for i in range(n):
cw[comp[i]] += treasure[i]
cadj = [set() for _ in range(cid)]
for u, v in roads:
if comp[u] != comp[v]:
cadj[comp[u]].add(comp[v])
memo = {}
def dp(cc):
if cc in memo:
return memo[cc]
best = 0
for sc in cadj[cc]:
best = max(best, dp(sc))
memo[cc] = cw[cc] + best
return memo[cc]
return dp(comp[start])
# --------------------------- basic / edge cases ---------------------------
def test_single_node_no_edges():
assert max_treasure(1, [7], [], 0) == 7
def test_single_node_with_self_loop():
assert max_treasure(1, [7], [(0, 0)], 0) == 7
def test_zero_value_node():
assert max_treasure(1, [0], [], 0) == 0
def test_simple_chain():
# 0 -> 1 -> 2, collect everything downstream
treasure = [1, 10, 100]
roads = [(0, 1), (1, 2)]
assert max_treasure(3, treasure, roads, 0) == 111
assert max_treasure(3, treasure, roads, 1) == 110
assert max_treasure(3, treasure, roads, 2) == 100
def test_two_node_cycle_is_one_scc():
# 0 <-> 1: both lootable from either start
assert max_treasure(2, [3, 4], [(0, 1), (1, 0)], 0) == 7
assert max_treasure(2, [3, 4], [(0, 1), (1, 0)], 1) == 7
def test_unreachable_treasure_excluded():
# node 2 holds a fortune but is unreachable from 0
treasure = [1, 1, 1000]
roads = [(0, 1)]
assert max_treasure(3, treasure, roads, 0) == 2
def test_pick_the_richer_branch():
# 0 -> 1 (value 5) and 0 -> 2 (value 50); only one branch is on a path
treasure = [1, 5, 50]
roads = [(0, 1), (0, 2)]
assert max_treasure(3, treasure, roads, 0) == 51
def test_branch_choice_favors_longer_sum():
# 0 -> 1 -> 3 (1+2+100) vs 0 -> 2 (1+50) ; note 3 unreachable via 2
treasure = [1, 2, 50, 100]
roads = [(0, 1), (1, 3), (0, 2)]
assert max_treasure(4, treasure, roads, 0) == 103
def test_scc_then_dag_tail():
# {0,1,2} form a cycle (sum 6), then 2 -> 3 (value 100)
treasure = [1, 2, 3, 100]
roads = [(0, 1), (1, 2), (2, 0), (2, 3)]
assert max_treasure(4, treasure, roads, 0) == 106
assert max_treasure(4, treasure, roads, 3) == 100
def test_multi_edges_and_self_loops_ignored():
treasure = [10, 20]
roads = [(0, 1), (0, 1), (0, 0), (1, 1)]
assert max_treasure(2, treasure, roads, 0) == 30
def test_diamond_shared_tail_counted_once():
# 0 -> 1 -> 3
# 0 -> 2 -> 3
# node 3 must be counted once, not twice
treasure = [1, 10, 20, 100]
roads = [(0, 1), (0, 2), (1, 3), (2, 3)]
assert max_treasure(4, treasure, roads, 0) == 1 + 20 + 100 # via 0->2->3
def test_start_in_middle_ignores_upstream():
treasure = [1000, 1, 1]
roads = [(0, 1), (1, 2)]
# starting at 1, the rich node 0 is upstream and unreachable
assert max_treasure(3, treasure, roads, 1) == 2
def test_two_cycles_joined():
# cycle A {0,1} -> cycle B {2,3}
treasure = [1, 1, 5, 5]
roads = [(0, 1), (1, 0), (1, 2), (2, 3), (3, 2)]
assert max_treasure(4, treasure, roads, 0) == 12
assert max_treasure(4, treasure, roads, 2) == 10
# --------------------------- randomized fuzz ---------------------------
def test_random_small_graphs_match_brute():
rng = random.Random(20260701)
for _ in range(600):
n = rng.randint(1, 8)
treasure = [rng.randint(0, 12) for _ in range(n)]
m = rng.randint(0, n * 2)
roads = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
start = rng.randrange(n)
expected = _brute(n, treasure, roads, start)
assert max_treasure(n, treasure, roads, start) == expected, (
n,
treasure,
roads,
start,
)
def test_random_dense_graphs_match_brute():
rng = random.Random(4242)
for _ in range(300):
n = rng.randint(3, 7)
treasure = [rng.randint(0, 20) for _ in range(n)]
roads = []
for u in range(n):
for v in range(n):
if u != v and rng.random() < 0.4:
roads.append((u, v))
start = rng.randrange(n)
expected = _brute(n, treasure, roads, start)
assert max_treasure(n, treasure, roads, start) == expected
# --------------------------- larger / performance ---------------------------
def test_large_chain():
n = 100_000
treasure = [1] * n
roads = [(i, i + 1) for i in range(n - 1)]
assert max_treasure(n, treasure, roads, 0) == n
assert max_treasure(n, treasure, roads, n // 2) == n - n // 2
def test_large_single_cycle():
n = 100_000
treasure = [1] * n
roads = [(i, (i + 1) % n) for i in range(n)]
# entire cycle is one SCC, all lootable from anywhere
assert max_treasure(n, treasure, roads, 0) == n
assert max_treasure(n, treasure, roads, 12345) == n
def test_large_deep_no_recursion_limit():
# A long chain would overflow a naive recursive SCC / DP; must be iterative.
n = 50_000
treasure = [2] * n
roads = [(i, i + 1) for i in range(n - 1)]
assert max_treasure(n, treasure, roads, 0) == 2 * n
def test_large_binary_tree_longest_root_to_leaf():
# complete binary tree, node i -> 2i+1, 2i+2; value = 1 everywhere.
# longest root path collects (deepest level + 1) nodes.
n = 1 << 16 # 65536 nodes
treasure = [1] * n
roads = []
for i in range(n):
for ch in (2 * i + 1, 2 * i + 2):
if ch < n:
roads.append((i, ch))
# expected = number of levels on the deepest greedy root-to-leaf walk
levels = 0
idx = 0
while idx < n:
levels += 1
idx = 2 * idx + 1
assert max_treasure(n, treasure, roads, 0) == levels
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.
Proposed solution
```python
from typing import Sequence, Tuple
def max_treasure(n: int, treasure: Sequence[int],
roads: Sequence[Tuple[int, int]], start: int) -> int:
"""
Computes the maximum total gold collectible on a walk starting at `start`
in a directed graph, where each node's gold is collected at most once.
"""
# 1. Identify Strongly Connected Components (SCCs)
# We use Kosaraju's algorithm (iterative) to find SCCs.
# This groups nodes that are mutually reachable.
# Build adjacency list for the original graph
adj = [[] for _ in range(n)]
for u, v in roads:
adj[u].append(v)
# Build adjacency list for the transposed graph
# (edges reversed) for the second pass of Kosaraju
radj = [[] for _ in range(n)]
for u, v in roads:
radj[v].append(u)
visited = [False] * n
order = []
# First pass: DFS to fill the order stack
# Iterative implementation to avoid recursion depth issues
for i in range(n):
if not visited[i]:
stack = [(i, 0)] # (node, next_child_index)
while stack:
node, idx = stack[-1]
if not visited[node]:
visited[node] = True
# Process neighbors
while idx < len(adj[node]):
neighbor = adj[node][idx]
stack[-1] = (node, idx + 1)
if not visited[neighbor]:
stack.append((neighbor, 0))
break
else:
# All neighbors processed
stack.pop()
order.append(node)
# Second pass: Process nodes in reverse order of finishing times
visited = [False] * n
comp_id = [0] * n
comp_size = 0
for node in reversed(order):
if not visited[node]:
# Start a new component
stack = [node]
visited[node] = True
comp_id[node] = comp_size
while stack:
curr = stack.pop()
for neighbor in radj[curr]:
if not visited[neighbor]:
visited[neighbor] = True
comp_id[neighbor] = comp_size
stack.append(neighbor)
comp_size += 1
# 2. Build the Condensed DAG
# Nodes are now the SCCs. We need to know which SCCs are reachable from the start SCC.
# Map from component index to the sum of treasure in that component
comp_treasure = [0] * comp_size
for i in range(n):
comp_treasure[comp_id[i]] += treasure[i]
# Build adjacency list for the condensed graph
# We need to deduplicate edges between components to avoid cycles in the DAG
# (though the condensed graph is a DAG by definition, duplicates don't hurt logic
# but we can skip them for efficiency)
comp_adj = [set() for _ in range(comp_size)]
for u, v in roads:
cu, cv = comp_id[u], comp_id[v]
if cu != cv:
comp_adj[cu].add(cv)
# Convert sets to lists for iteration
comp_adj = [list(s) for s in comp_adj]
# 3. Topological Sort and DP on the DAG
# We need to find the maximum treasure reachable from the start component.
# Kahn's algorithm for topological sort
in_degree = [0] * comp_size
for u in range(comp_size):
for v in comp_adj[u]:
in_degree[v] += 1
# Queue for nodes with zero in-degree
from collections import deque
q = deque([i for i in range(comp_size) if in_degree[i] == 0])
# We only care about components reachable from start.
# We can perform a BFS/DFS restricted to the reachable subgraph.
# Initialize reachable set
reachable = [False] * comp_size
reachable[comp_id[start]] = True
# Process nodes in topological order
# We use a modified Kahn's algorithm that only propagates from reachable nodes.
# We need to track which nodes are processed to avoid re-adding to queue.
processed = [False] * comp_size
# We can use a queue for nodes to process.
# Start with the start component.
q.append(comp_id[start])
while q:
u = q.popleft()
if processed[u]:
continue
processed[u] = True
for v in comp_adj[u]:
# If v is reachable from u, it becomes reachable from start.
# We don't need to update in_degree for the purpose of finding max treasure,
# because we are just traversing the DAG.
# However, we must ensure we don't process v multiple times.
# Since the graph is a DAG, processing u once is enough.
# But we need to ensure we process v if it becomes reachable.
# Standard Kahn's removes edges. Here we just want to visit.
# We can simply add v to the queue if it's not processed.
# But we must ensure we don't add it multiple times.
# Since we don't decrement in_degree, we might add v multiple times.
# To fix this, we can check if v is reachable.
# If v is reachable, we should process it.
# If v is not reachable, we don't care.
# Actually, we can just use a simple DFS/BFS from start.
# Since the graph is a DAG, we can just traverse.
# But we need to ensure we don't get stuck in a loop (though it's a DAG).
# We can use a visited set for components.
# Let's use a simple BFS.
pass
# Let's use a simple BFS/DFS from the start component.
# Since the condensed graph is a DAG, we can just traverse.
# We need to avoid re-visiting components.
stack = [comp_id[start]]
visited_comp = [False] * comp_size
visited_comp[comp_id[start]] = True
max_gold = 0
while stack:
u = stack.pop()
max_gold += comp_treasure[u]
for v in comp_adj[u]:
if not visited_comp[v]:
visited_comp[v] = True
stack.append(v)
return max_gold
```Test output (stdout)
.
Errors (stderr)
[TIMEOUT]
Self-repair attempts
[
{
"total": 1,
"answer": "```python\nfrom typing import Sequence, Tuple\n\ndef max_treasure(n: int, treasure: Sequence[int],\n roads: Sequence[Tuple[int, int]], start: int) -> int:\n \"\"\"\n Computes the maximum total gold collectible on a walk starting at `start`\n in a directed graph, where each node's gold is collected at most once.\n \"\"\"\n # 1. Identify Strongly Connected Components (SCCs)\n # We use Kosaraju's algorithm (iterative) to find SCCs.\n # This groups nodes that are mutually reachable.\n \n # Build adjacency list for the original graph\n adj = [[] for _ in range(n)]\n for u, v in roads:\n adj[u].append(v)\n \n # Build adjacency list for the transposed graph\n # (edges reversed) for the second pass of Kosaraju\n radj = [[] for _ in range(n)]\n for u, v in roads:\n radj[v].append(u)\n \n visited = [False] * n\n order = []\n \n # First pass: DFS to fill the order stack\n # Iterative implementation to avoid recursion depth issues\n for i in range(n):\n if not visited[i]:\n stack = [(i, 0)] # (node, next_child_index)\n while stack:\n node, idx = stack[-1]\n if not visited[node]:\n visited[node] = True\n # Process neighbors\n while idx < len(adj[node]):\n neighbor = adj[node][idx]\n stack[-1] = (node, idx + 1)\n if not visited[neighbor]:\n stack.append((neighbor, 0))\n break\n else:\n # All neighbors processed\n stack.pop()\n order.append(node)\n \n # Second pass: Process nodes in reverse order of finishing times\n visited = [False] * n\n comp_id = [0] * n\n comp_size = 0\n \n for node in reversed(order):\n if not visited[node]:\n # Start a new component\n stack = [node]\n visited[node] = True\n comp_id[node] = comp_size\n while stack:\n curr = stack.pop()\n for neighbor in radj[curr]:\n if not visited[neighbor]:\n visited[neighbor] = True\n comp_id[neighbor] = comp_size\n stack.append(neighbor)\n comp_size += 1\n \n # 2. Build the Condensed DAG\n # Nodes are now the SCCs. We need to know which SCCs are reachable from the start SCC.\n \n # Map from component index to the sum of treasure in that component\n comp_treasure = [0] * comp_size\n for i in range(n):\n comp_treasure[comp_id[i]] += treasure[i]\n \n # Build adjacency list for the condensed graph\n # We need to deduplicate edges between components to avoid cycles in the DAG\n # (though the condensed graph is a DAG by definition, duplicates don't hurt logic\n # but we can skip them for efficiency)\n comp_adj = [set() for _ in range(comp_size)]\n for u, v in roads:\n cu, cv = comp_id[u], comp_id[v]\n if cu != cv:\n comp_adj[cu].add(cv)\n \n # Convert sets to lists for iteration\n comp_adj = [list(s) for s in comp_adj]\n \n # 3. Topological Sort and DP on the DAG\n # We need to find the maximum treasure reachable from the start component.\n \n # Kahn's algorithm for topological sort\n in_degree = [0] * comp_size\n for u in range(comp_size):\n for v in comp_adj[u]:\n in_degree[v] += 1\n \n # Queue for nodes with zero in-degree\n from collections import deque\n q = deque([i for i in range(comp_size) if in_degree[i] == 0])\n \n # We only care about components reachable from start.\n # We can perform a BFS/DFS restricted to the reachable subgraph.\n \n # Initialize reachable set\n reachable = [False] * comp_size\n reachable[comp_id[start]] = True\n \n # Process nodes in topological order\n # We use a modified Kahn's algorithm that only propagates from reachable nodes.\n \n # We need to track which nodes are processed to avoid re-adding to queue.\n processed = [False] * comp_size\n \n # We can use a queue for nodes to process.\n # Start with the start component.\n q.append(comp_id[start])\n \n while q:\n u = q.popleft()\n if processed[u]:\n continue\n processed[u] = True\n \n for v in comp_adj[u]:\n # If v is reachable from u, it becomes reachable from start.\n # We don't need to update in_degree for the purpose of finding max treasure,\n # because we are just traversing the DAG.\n # However, we must ensure we don't process v multiple times.\n # Since the graph is a DAG, processing u once is enough.\n # But we need to ensure we process v if it becomes reachable.\n # Standard Kahn's removes edges. Here we just want to visit.\n # We can simply add v to the queue if it's not processed.\n # But we must ensure we don't add it multiple times.\n # Since we don't decrement in_degree, we might add v multiple times.\n # To fix this, we can check if v is reachable.\n # If v is reachable, we should process it.\n # If v is not reachable, we don't care.\n \n # Actually, we can just use a simple DFS/BFS from start.\n # Since the graph is a DAG, we can just traverse.\n # But we need to ensure we don't get stuck in a loop (though it's a DAG).\n # We can use a visited set for components.\n \n # Let's use a simple BFS.\n pass\n \n # Let's use a simple BFS/DFS from the start component.\n # Since the condensed graph is a DAG, we can just traverse.\n # We need to avoid re-visiting components.\n \n stack = [comp_id[start]]\n visited_comp = [False] * comp_size\n visited_comp[comp_id[start]] = True\n \n max_gold = 0\n \n while stack:\n u = stack.pop()\n max_gold += comp_treasure[u]\n \n for v in comp_adj[u]:\n if not visited_comp[v]:\n visited_comp[v] = True\n stack.append(v)\n \n return max_gold\n```",
"passed": 0,
"test_error": ".\n\n[TIMEOUT]"
},
{
"total": 1,
"answer": "```python\nfrom typing import Sequence, Tuple\n\ndef max_treasure(n: int, treasure: Sequence[int],\n roads: Sequence[Tuple[int, int]], start: int) -> int:\n \"\"\"\n Computes the maximum total gold collectible on a walk starting at `start`\n in a directed graph, where each node's gold is collected at most once.\n \"\"\"\n # 1. Identify Strongly Connected Components (SCCs)\n # We use Kosaraju's algorithm (iterative) to find SCCs.\n # This groups nodes that are mutually reachable.\n \n # Build adjacency list for the original graph\n adj = [[] for _ in range(n)]\n for u, v in roads:\n adj[u].append(v)\n \n # Build adjacency list for the transposed graph\n # (edges reversed) for the second pass of Kosaraju\n radj = [[] for _ in range(n)]\n for u, v in roads:\n radj[v].append(u)\n \n visited = [False] * n\n order = []\n \n # First pass: DFS to fill the order stack\n # Iterative implementation to avoid recursion depth issues\n for i in range(n):\n if not visited[i]:\n stack = [(i, 0)] # (node, next_child_index)\n while stack:\n node, idx = stack[-1]\n if not visited[node]:\n visited[node] = True\n # Process neighbors\n while idx < len(adj[node]):\n neighbor = adj[node][idx]\n stack[-1] = (node, idx + 1)\n if not visited[neighbor]:\n stack.append((neighbor, 0))\n break\n else:\n # All neighbors processed\n stack.pop()\n order.append(node)\n \n # Second pass: Process nodes in reverse order of finishing times\n visited = [False] * n\n comp_id = [0] * n\n comp_size = 0\n \n for node in reversed(order):\n if not visited[node]:\n # Start a new component\n stack = [node]\n visited[node] = True\n comp_id[node] = comp_size\n while stack:\n curr = stack.pop()\n for neighbor in radj[curr]:\n if not visited[neighbor]:\n visited[neighbor] = True\n comp_id[neighbor] = comp_size\n stack.append(neighbor)\n comp_size += 1\n \n # 2. Build the Condensed DAG\n # Nodes are now the SCCs. We need to know which SCCs are reachable from the start SCC.\n \n # Map from component index to the sum of treasure in that component\n comp_treasure = [0] * comp_size\n for i in range(n):\n comp_treasure[comp_id[i]] += treasure[i]\n \n # Build adjacency list for the condensed graph\n # We need to deduplicate edges between components to avoid cycles in the DAG\n # (though the condensed graph is a DAG by definition, duplicates don't hurt logic\n # but we can skip them for efficiency)\n comp_adj = [set() for _ in range(comp_size)]\n for u, v in roads:\n cu, cv = comp_id[u], comp_id[v]\n if cu != cv:\n comp_adj[cu].add(cv)\n \n # Convert sets to lists for iteration\n comp_adj = [list(s) for s in comp_adj]\n \n # 3. Topological Sort and DP on the DAG\n # We need to find the maximum treasure reachable from the start component.\n \n # Kahn's algorithm for topological sort\n in_degree = [0] * comp_size\n for u in range(comp_size):\n for v in comp_adj[u]:\n in_degree[v] += 1\n \n # Queue for nodes with zero in-degree\n from collections import deque\n q = deque([i for i in range(comp_size) if in_degree[i] == 0])\n \n # We only care about components reachable from start.\n # We can perform a BFS/DFS restricted to the reachable subgraph.\n \n # Initialize reachable set\n reachable = [False] * comp_size\n reachable[comp_id[start]] = True\n \n # Process nodes in topological order\n # We use a modified Kahn's algorithm that only propagates from reachable nodes.\n \n # We need to track which nodes are processed to avoid re-adding to queue.\n processed = [False] * comp_size\n \n # We can use a queue for nodes to process.\n # Start with the start component.\n q.append(comp_id[start])\n \n while q:\n u = q.popleft()\n if processed[u]:\n continue\n processed[u] = True\n \n for v in comp_adj[u]:\n # If v is reachable from u, it becomes reachable from start.\n # We don't need to update in_degree for the purpose of finding max treasure,\n # because we are just traversing the DAG.\n # However, we must ensure we don't process v multiple times.\n # Since the graph is a DAG, processing u once is enough.\n # But we need to ensure we process v if it becomes reachable.\n # Standard Kahn's removes edges. Here we just want to visit.\n # We can simply add v to the queue if it's not processed.\n # But we must ensure we don't add it multiple times.\n # Since we don't decrement in_degree, we might add v multiple times.\n # To fix this, we can check if v is reachable.\n # If v is reachable, we should process it.\n # If v is not reachable, we don't care.\n \n # Actually, we can just use a simple DFS/BFS from start.\n # Since the graph is a DAG, we can just traverse.\n # We need to ensure we don't get stuck in a loop (though it's a DAG).\n # We can use a visited set for components.\n \n # Let's use a simple BFS.\n pass\n \n # Let's use a simple BFS/DFS from the start component.\n # Since the condensed graph is a DAG, we can just traverse.\n # We need to avoid re-visiting components.\n \n stack = [comp_id[start]]\n visited_comp = [False] * comp_size\n visited_comp[comp_id[start]] = True\n \n max_gold = 0\n \n while stack:\n u = stack.pop()\n max_gold += comp_treasure[u]\n \n for v in comp_adj[u]:\n if not visited_comp[v]:\n visited_comp[v] = True\n stack.append(v)\n \n return max_gold\n```",
"passed": 0,
"test_error": ".\n\n[TIMEOUT]"
},
{
"total": 1,
"answer": "```python\nfrom typing import Sequence, Tuple\n\ndef max_treasure(n: int, treasure: Sequence[int],\n roads: Sequence[Tuple[int, int]], start: int) -> int:\n \"\"\"\n Computes the maximum total gold collectible on a walk starting at `start`\n in a directed graph, where each node's gold is collected at most once.\n \"\"\"\n # 1. Identify Strongly Connected Components (SCCs)\n # We use Kosaraju's algorithm (iterative) to find SCCs.\n # This groups nodes that are mutually reachable.\n \n # Build adjacency list for the original graph\n adj = [[] for _ in range(n)]\n for u, v in roads:\n adj[u].append(v)\n \n # Build adjacency list for the transposed graph\n # (edges reversed) for the second pass of Kosaraju\n radj = [[] for _ in range(n)]\n for u, v in roads:\n radj[v].append(u)\n \n visited = [False] * n\n order = []\n \n # First pass: DFS to fill the order stack\n # Iterative implementation to avoid recursion depth issues\n for i in range(n):\n if not visited[i]:\n stack = [(i, 0)] # (node, next_child_index)\n while stack:\n node, idx = stack[-1]\n if not visited[node]:\n visited[node] = True\n # Process neighbors\n while idx < len(adj[node]):\n neighbor = adj[node][idx]\n stack[-1] = (node, idx + 1)\n if not visited[neighbor]:\n stack.append((neighbor, 0))\n break\n else:\n # All neighbors processed\n stack.pop()\n order.append(node)\n \n # Second pass: Process nodes in reverse order of finishing times\n visited = [False] * n\n comp_id = [0] * n\n comp_size = 0\n \n for node in reversed(order):\n if not visited[node]:\n # Start a new component\n stack = [node]\n visited[node] = True\n comp_id[node] = comp_size\n while stack:\n curr = stack.pop()\n for neighbor in radj[curr]:\n if not visited[neighbor]:\n visited[neighbor] = True\n comp_id[neighbor] = comp_size\n stack.append(neighbor)\n comp_size += 1\n \n # 2. Build the Condensed DAG\n # Nodes are now the SCCs. We need to know which SCCs are reachable from the start SCC.\n \n # Map from component index to the sum of treasure in that component\n comp_treasure = [0] * comp_size\n for i in range(n):\n comp_treasure[comp_id[i]] += treasure[i]\n \n # Build adjacency list for the condensed graph\n # We need to deduplicate edges between components to avoid cycles in the DAG\n # (though the condensed graph is a DAG by definition, duplicates don't hurt logic\n # but we can skip them for efficiency)\n comp_adj = [set() for _ in range(comp_size)]\n for u, v in roads:\n cu, cv = comp_id[u], comp_id[v]\n if cu != cv:\n comp_adj[cu].add(cv)\n \n # Convert sets to lists for iteration\n comp_adj = [list(s) for s in comp_adj]\n \n # 3. Topological Sort and DP on the DAG\n # We need to find the maximum treasure reachable from the start component.\n \n # Kahn's algorithm for topological sort\n in_degree = [0] * comp_size\n for u in range(comp_size):\n for v in comp_adj[u]:\n in_degree[v] += 1\n \n # Queue for nodes with zero in-degree\n from collections import deque\n q = deque([i for i in range(comp_size) if in_degree[i] == 0])\n \n # We only care about components reachable from start.\n # We can perform a BFS/DFS restricted to the reachable subgraph.\n \n # Initialize reachable set\n reachable = [False] * comp_size\n reachable[comp_id[start]] = True\n \n # Process nodes in topological order\n # We use a modified Kahn's algorithm that only propagates from reachable nodes.\n \n # We need to track which nodes are processed to avoid re-adding to queue.\n processed = [False] * comp_size\n \n # We can use a queue for nodes to process.\n # Start with the start component.\n q.append(comp_id[start])\n \n while q:\n u = q.popleft()\n if processed[u]:\n continue\n processed[u] = True\n \n for v in comp_adj[u]:\n # If v is reachable from u, it becomes reachable from start.\n # We don't need to update in_degree for the purpose of finding max treasure,\n # because we are just traversing the DAG.\n # However, we must ensure we don't process v multiple times.\n # Since the graph is a DAG, processing u once is enough.\n # But we need to ensure we process v if it becomes reachable.\n # Standard Kahn's removes edges. Here we just want to visit.\n # We can simply add v to the queue if it's not processed.\n # But we must ensure we don't add it multiple times.\n # Since we don't decrement in_degree, we might add v multiple times.\n # To fix this, we can check if v is reachable.\n # If v is reachable, we should process it.\n # If v is not reachable, we don't care.\n \n # Actually, we can just use a simple DFS/BFS from start.\n # Since the graph is a DAG, we can just traverse.\n # We need to ensure we don't get stuck in a loop (though it's a DAG).\n # We can use a visited set for components.\n \n # Let's use a simple BFS.\n pass\n \n # Let's use a simple BFS/DFS from the start component.\n # Since the condensed graph is a DAG, we can just traverse.\n # We need to avoid re-visiting components.\n \n stack = [comp_id[start]]\n visited_comp = [False] * comp_size\n visited_comp[comp_id[start]] = True\n \n max_gold = 0\n \n while stack:\n u = stack.pop()\n max_gold += comp_treasure[u]\n \n for v in comp_adj[u]:\n if not visited_comp[v]:\n visited_comp[v] = True\n stack.append(v)\n \n return max_gold\n```",
"passed": 0,
"test_error": ""
}
]