unreasonably effective

link Backtrack A valid itinerary uses each ticket exactly once and is lexicographically sorted. So, we build a directed graph where an edge is a ticket. Starting with “JFK” we backtrack to find a path that consumes all tickets. Each hop of the path consumes one available ticket. We use sorted edge-lists so that possible…

link Change of routes is what we care about, bus-stops within a route can be abstracted away. We thus have an undirected graph where vertices are route indices and there is an edge if the two routes share a bus-stop. In this route graph, we want to find the shortest distance between two routes: one…

link A tree has barely enough edges to remain connected. So, with nodes there must be edges and all nodes must belong to a single connected component. We use DFS for the connected component part. Time: , space:

link We can piggyback on DFS to clone the graph. We copy a node when we explore it. Note, if a shallow reference of exists in the map, we should grab that reference and deepen it. Otherwise, an earlier node storing ‘s reference in its neighbors list, will not be able to access the updated,…

link Backtrack A 3-cycle like below consists of a 3-room path () and an edge from the last room to the first room (). So, we consider each room as the head of a possible 3-cycle, generate 3-length path and check if there is an edge from last room to first. If largest number of…

link We use Dijkstra’s shortest path distance algorithm to find delays to all nodes from source. Max distance from source is the minimum time it would take for the signal to reach all nodes. heapq does not allow updating key, so we insert new entries like (d_v, v) whenever there is a better distance and…