Validate a Parent-Child Forest

Validate a Parent-Child Forest

You are given a list of edges representing a collection of directed trees (a forest). Each edge is represented as a list or tuple [parent, child]. A valid forest must satisfy the following conditions:

1. Every node has at most one parent.
2. There are no directed cycles.
3. Every node in the forest is part of at least one valid parent-child relationship or is a standalone root node (if specified in the input nodes list).

Given a list of nodes nodes (all unique identifiers) and a list of edges edges (where edges[i] = [parent, child]), write a function is_valid_forest(nodes, edges) that returns True if the structure forms a valid forest and False otherwise.

Function Signature

def is_valid_forest(nodes: List[int], edges: List[List[int]]) -> bool:

Examples

Example 1: Input: nodes = [1, 2, 3, 4], edges = [[1, 2], [1, 3]] Output: True Explanation: Node 1 is the root for a tree containing 2 and 3. Node 4 is a standalone tree. This is a valid forest.

Example 2: Input: nodes = [1, 2, 3], edges = [[1, 2], [2, 1]] Output: False Explanation: There is a cycle between 1 and 2.

Example 3: Input: nodes = [1, 2, 3], edges = [[1, 2], [3, 2]] Output: False Explanation: Node 2 has two parents (1 and 3), which violates the tree definition.

Constraints

• 1 <= len(nodes) <= 10,000
• 0 <= len(edges) <= 10,000
• Nodes are positive integers.
• The input edges may contain nodes not present in nodes (these are considered invalid).