Validate Adding an Edge to a Directed Acyclic Graph

Problem Statement

You are given a Directed Acyclic Graph (DAG) represented by an adjacency list graph, where graph[u] contains a list of all nodes v such that there is a directed edge from u to v.

You are tasked with implementing a function can_add_edge(n, graph, u, v) that determines if a directed edge from node u to node v can be added without violating the DAG property. The graph contains n nodes labeled from 0 to n-1.

Rules for validation:

1. No Self-Loops: You cannot add an edge where u == v.
2. No Duplicates: You cannot add an edge if the directed edge (u, v) already exists.
3. No Cycles: You cannot add the edge (u, v) if there is already a path from v to u in the graph.

Function Signature

def can_add_edge(n: int, graph: dict, u: int, v: int) -> bool:

Constraints

• 0 <= u, v < n
• n can be up to 10,000.
• graph is guaranteed to be a valid DAG initially.

Examples

Example 1

• Input: n = 3, graph = {0: [1], 1: [2], 2: []}, u = 0, v = 2
• Output: True
• Explanation: Adding edge 0->2 does not create a cycle. The path 0->1->2 is valid.

Example 2

• Input: n = 3, graph = {0: [1], 1: [2], 2: [0]}, u = 2, v = 1
• Output: False
• Explanation: Adding edge 2->1 would create a cycle because 1 can already reach 2.

Edge Cases

• Disconnected graphs.
• Adding an edge between nodes that have no pre-existing paths.