Problem
Given a directed graph of city-to-city connections (edges), find the path (itinerary) that visits the maximum number of unique cities. Each edge is a valid direct connection; the goal is a simple path (no repeated cities) that maximizes the number of distinct cities visited.
Input / Output
- Input: a set of cities and directed edges between them.
- Output: the itinerary (ordered list of cities) visiting the most unique cities, or just its length.
Constraints
- No city may repeat in a path (simple path).
- Assume the graph is a DAG (cycle-free) unless told otherwise — with cycles this is the NP-hard longest-simple-path problem.
- The graph may be disconnected, so any city can be a start.
Example
- Cities A,B,C,D with edges A->B, B->C, A->D -> the longest itinerary is A->B->C (3 cities).