Detect Cycles in Config Graph

MediumPython

Problem

Freshservice configuration items can depend on other items, forming a directed configuration graph. Given these dependencies, detect whether the graph contains a cycle and return one cycle path.

Implement find_dependency_cycle(config) using iterative depth-first search. The input maps each configuration item to the items it directly depends on. If a cycle exists, return a list of item names containing the repeated starting item at both ends. If the graph is acyclic, return [].

A dependency on an item that is not itself a key in config represents a leaf item and must still be processed. The graph may be disconnected. Return any one valid cycle when multiple cycles exist.

Formal Specification

Input: config, a dictionary whose keys and values are strings. Each key maps to a list of directly dependent item names.
Output: A list of strings representing one directed cycle, with the first item repeated at the end, or an empty list if no cycle exists.
An edge A -> B means that A depends on B.

Constraints

1 <= len(config) <= 10^5
The total number of dependency edges is at most 2 * 10^5
Item names are non-empty strings
Each dependency list contains no duplicate item names
Referenced items may be absent from config and are treated as leaves

Function Signature

def find_dependency_cycle(config):

Freshservice configuration items can depend on other items, forming a directed configuration graph. Given these dependencies, detect whether the graph contains a cycle and return one cycle path.

A dependency on an item that is not itself a key in config represents a leaf item and must still be processed. The graph may be disconnected. Return any one valid cycle when multiple cycles exist.

Formal Specification

Input: config, a dictionary whose keys and values are strings. Each key maps to a list of directly dependent item names.
Output: A list of strings representing one directed cycle, with the first item repeated at the end, or an empty list if no cycle exists.
An edge A -> B means that A depends on B.