Check if adding edge creates cycle in digraph
Overview
This question evaluates understanding of graph algorithms, reachability, and algorithmic complexity by determining whether adding a directed edge would introduce a cycle in an otherwise acyclic directed graph.
You work with a system that stores items and directed relationships between them (for example, item A points to item B). The relationships form a directed graph that is guaranteed to be acyclic (there are no directed cycles, so following pointers will never lead to an infinite loop).
Whenever a user creates a new relationship between two items, you add a new directed edge (u_new, v_new). Before committing this change, you must validate that the graph will still contain no directed cycles after adding this edge.
Design an algorithm and write code for a function that takes:
- an integer n: the number of items labeled from 0 to n - 1,
- a list of existing directed edges, where each edge is a pair (u, v) meaning a directed edge from u to v,
- a candidate new directed edge (u_new, v_new),
and returns a boolean indicating whether adding this new edge keeps the graph acyclic (true) or would introduce at least one directed cycle (false).
State the time and space complexity of your approach. Assume n and the number of edges can each be as large as 100000, so your solution should be close to linear in the size of the graph.