Implement a function that finds the length of the longest simple path (no repeated nodes) in an undirected small graph given as adjacency lists. Return the length in number of edges for the longest path; if the graph has no edges, return 0. The function should be efficient for up to about 15 nodes and handle disconnected graphs by evaluating each component.
Examples:
longest_path_length(adj)returns4for a path of 5 nodes connected in sequencelongest_path_length({1:[2,3],2:[1,3],3:[1,2]})returns2- Edge case: a graph with a single node and no edges returns
0
def longest_path_length(adj):
"""Compute the length of the longest simple path in an undirected graph.
Parameters:
adj: dict[int, list[int]] - adjacency list of the graph
Returns:
int - number of edges in the longest simple path
"""
pass
Rules:
- Any language or pseudocode is fine. The stub just shows the shape.
- Say the time complexity of your approach.
- one well-defined function with a clear input and output
- 2 or 3 sample calls with expected results, including an edge case
- size suitable for an interview warm-up
Post your solution as a reply. Answer goes up in about a day.