BackmediumUncategorized uncategorized medium

Longest Path Visiting All Nodes with Ordered Subsequence Solution

Problem Statement

Given a directed graph with `n` nodes, represented by a list of `edges`, and a list of `ordered_nodes`, find the length of the longest path that visits every node exactly once. Additionally, the nodes specified in `ordered_nodes` must appear in the path in the exact relative order as they appear in the `ordered_nodes` list. If no such path exists, return -1. The nodes are 0-indexed.

Example 1
Input
n = 5 edges = [[0, 1], [1, 2], [2, 3], [3, 4], [0, 3], [1, 4]] ordered_nodes = [0, 2, 4]
Output
4

Explanation: The path 0 -> 1 -> 2 -> 3 -> 4 visits all nodes exactly once. Nodes 0, 2, and 4 appear in the specified order. The length of this path is 4.

Constraints

  • `2 <= n <= 15`
  • `0 <= edges.length <= n * (n - 1)`
  • `0 <= u, v < n` for each edge `(u, v)`
  • `1 <= ordered_nodes.length <= n`
  • All elements in `ordered_nodes` are distinct and within `[0, n-1]`.

More Uncategorized Problems

Cost-Optimized Directed FlowmediumLongest Path Visiting All Nodes with Ordered SubsequencemediumMinimum Elements for Target SummediumMaximum Subset with Three Resource Constraintsmedium
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free