Find the itinerary with the most visited unique cities

Question

## Find the Itinerary with the Most Visited Unique Cities

Given a directed graph of city-to-city connections (edges), find the path (itinerary) that visits the maximum number of **unique** cities. Each edge represents a valid direct connection between two cities, and the goal is to find a simple path (no repeated cities) through this graph that maximizes the number of distinct cities visited.

### Problem Framing
Model the input as a **directed acyclic graph (DAG)** where each city is a node and each allowed route is a directed edge. The task reduces to finding the **longest path in a DAG** by number of nodes. If cycles exist, the problem becomes NP-hard (longest simple path in a general graph), but interviewers typically expect a DAG assumption or cycle-free input.

### Approach
- **Naïve DFS from every node** explores all paths but has O(N²) or worse complexity due to repeated subproblem computation.
- **Memoization (top-down DP):** For each node, cache the length of the longest path starting from that node. When revisiting a node during DFS, return the cached value. This reduces the time complexity to **O(V + E)** where V = cities and E = connections.
- **Topological sort + bottom-up DP:** Process nodes in reverse topological order and propagate longest-path lengths. Also O(V + E) and avoids recursion stack overhead.
- To reconstruct the actual itinerary (not just the length), store the next city on the optimal path alongside the cached length.

### Edge Cases & Follow-ups
- **Cycles:** If cycles are present, simple memoization breaks (infinite recursion or incorrect results). Detect cycles with a visited/in-stack set. Interviewers may not require handling this.
- **Multiple equally long itineraries:** Decide whether to return all or any one.
- **Disconnected graph:** Must try DFS/DP from every node as a potential start.
- **Space complexity:** O(V) for memoization table and recursion stack.
- **Time complexity:** O(V + E) with memoization on a DAG.

This question tests graph modeling, DFS with memoization, and the ability to recognize overlapping subproblems — a blend of graph theory and dynamic programming thinking.