Find the tools every route to payments crosses
Your task
Your support agent's tools feed each other: a link from tool a to tool b means the output of a can end up in the input of b. Untrusted email enters at one tool, and the payment tool moves money. You want to put one guard on a tool that every route from the email tool to the payment tool passes through.
Write choke_points(n, links, source, target) that returns every such tool.
Input and output:
n: the number of tools, 2 to 100,000, numbered 0 ton - 1.links: up to 200,000 pairs[a, b], each a link from toolato toolb. A link goes one way only. A pair can repeat, andacan equalb.source: the tool where email enters.target: the payment tool. They are different tools.- Return a list of tools in increasing order.
Rules:
- A route is a sequence of tools that starts at
source, ends attarget, and has a link from each tool to the next. - Return every tool other than
sourceandtargetthat is on every route. - If there is no route at all, return an empty list.
Examples
choke_points(n: int, links: list[list[int]], source: int, target: int) -> list[int]choke_points(6, [[0, 1], [1, 2], [1, 3], [2, 4], [3, 4], [4, 5]], 0, 5)[1, 4]choke_points(4, [[0, 1], [1, 2], [3, 2]], 0, 3)[]choke_points(4, [[0, 1], [1, 2], [2, 1], [2, 3]], 0, 3)[1, 2]About this question
Find the tools every route to payments crosses
Model answer
Free on every accountApproach
A tool on every route is on any one route you pick. So find one route with a search from source, and return an empty list if there is none. Only the tools on that route can be answers, and the question becomes: for which of them is there no way around?
Walk the route from source to target, keeping reach, the furthest position on the route that anything searched so far can get to. Standing at position i, if reach is at most i, nothing behind you can get past this tool, so it is an answer. Then search outward from this tool: follow its links through tools off the route. When the search touches a tool on the route at position p, raise reach to p if that is further, and do not go on through it, since that tool has its own turn. Mark each off-route tool as visited once, and never clear the marks during the walk. A tool searched from an earlier position has already counted all its exits, and reach never falls, so nothing is lost. That is what makes the walk linear.
Why it is right. Suppose some route avoids the tool at position i. Take the last tool it visits at a position before i. From there it goes through off-route tools until it lands on a position past i, so reach was already past i when you arrived. Going the other way, if reach is past i, some earlier position leads to a later one through off-route tools only, and with the route's first and last stretches that makes a route that avoids this tool.
These tools are the dominators of target in the graph searched from source. The Lengauer-Tarjan algorithm finds the whole dominator tree, but for one target the walk is enough.
Why the obvious approaches fail
- Deleting each route tool and searching again is correct, and it takes about 5 billion steps on a chain of 100,000 tools.
- Taking the tools on every shortest route is wrong: a longer route can go around a tool that every shortest route uses.
- Taking a tool that stands alone at its distance from
sourcefails the same way. - Articulation points treat links as two-way, and here direction decides whether a link is a way around.
- Counting a way around only when a link joins two route tools directly misses a detour through off-route tools.
Complexity
O(n + m) time for n tools and m links: each tool is searched once and each link is read at most twice. O(n + m) space.
The code for this answer is in the Reference solution tab, on the plan.The code for this answer is in the Reference solution tab.