Cycle Detection in a Directed Graph

You are given a directed graph and your task is to detect whether the graph contains a cycle.

The graph is represented using an adjacency list. Each node in the graph is identified by a string label. For each node, you are given the number of its neighbors followed by the neighbor labels.

A cycle in a directed graph is a non-empty sequence of distinct nodes \(v_1, v_2, \ldots, v_k\) such that there is an edge from \(v_i\) to \(v_{i+1}\) for \(1 \le i < k\) and an edge from \(v_k\) back to \(v_1\). If such a cycle exists, output True; otherwise, output False.

Implement the cycle detection using Depth-First Search (DFS) along with a recursion stack to track the current path of exploration.

inputFormat

The first line contains an integer \(m\) representing the number of nodes in the graph. The next \(m\) lines each describe a node. Each such line begins with a node label (a string), followed by an integer \(k\) which is the number of neighbors for that node, followed by \(k\) neighbor labels separated by spaces.

For example, a line A 1 B indicates that node "A" has one neighbor: "B".

outputFormat

Output a single line: True if the graph contains a cycle, and False otherwise.

3
A 1 B
B 1 C
C 1 A

True