Resolve Short-Link Redirect Chains That May Loop

A URL shortener lets owners point a short code at another short code, so a visitor may be bounced through several hops before landing. Every code has at most one outgoing redirect. Misconfigurations happen: chains can loop back on themselves.

You are given the redirect table as a list of (source, target) pairs, where no source appears twice.

Part 1: Resolve one code

def resolve_link(start: str, redirects: list[tuple[str, str]]) -> str:

Simulate the visitor:

• The visitor begins at start, which counts as visited.
• If the current code has no redirect, stop and return it.
• Otherwise look at its target. If the target has not been visited, move there and mark it visited.
• If the target has been visited, following it would loop. Stop without following it and return the current code: the last code reached before the loop closes.

Example

redirects = [("k7","m2"), ("m2","q9"), ("q9","t4"), ("t4","m2"),
             ("b3","k7"), ("x1","z8"), ("z8","p5"), ("w0","w0")]

resolve_link("x1", redirects)   -> "p5"    x1 -> z8 -> p5, and p5 has no redirect
resolve_link("b3", redirects)   -> "t4"    b3 -> k7 -> m2 -> q9 -> t4, and t4 points back to m2
resolve_link("q9", redirects)   -> "m2"    q9 -> t4 -> m2, and m2 points to q9 (already visited)
resolve_link("w0", redirects)   -> "w0"    self-redirect
resolve_link("nope", redirects) -> "nope"  unknown code, no redirect

The loop does not have to include start. In the b3 case the visitor passes through b3 and k7 before entering the loop m2 -> q9 -> t4.

Part 2: Resolve many codes

An audit job needs the answer for a large batch of start codes.

def resolve_all(redirects: list[tuple[str, str]], queries: list[str]) -> list[str]:

Return the Part 1 answer for every query, in order. Make the total work O(V + Q), where V is the number of distinct codes and Q is the number of queries. Re-walking the chain for each query, which is O(V * Q) in the worst case, is too slow.

resolve_all(redirects, ["b3", "k7", "m2", "t4"]) -> ["t4", "t4", "t4", "q9"]

Constraints

• 0 <= len(redirects) <= 2 * 10^5, and each source appears at most once.
• Codes are non-empty alphanumeric strings. A query may name a code that appears nowhere in the table.
• 1 <= len(queries) <= 2 * 10^5.