ServiceNow CMDB CI Relationship Graph: Cycle Detection
Problem Statement
In the ServiceNow Configuration Management Database (CMDB), Configuration Items (CIs) such as Servers, Databases, and Web Applications form a dependency graph.
A valid infrastructure dependency hierarchy must be a **Directed Acyclic Graph (DAG)**. Circular dependencies cause infinite cascade loops during automated incident root cause analysis.
Given `numCis` items (labeled `0` to `numCis - 1`) and an array of directed relationships `[u, v]` (meaning CI `u` depends on CI `v`), detect whether a circular dependency cycle exists.
### Input Format
- First line contains two integers: `numCis` and `numRelationships`.
- The next `numRelationships` lines each contain two integers: `u v`.
### Output Format
- Print `true` if a circular dependency is detected, or `false` if the graph is a valid DAG.
### Constraints
- `1 <= numCis <= 10^4`
- `0 <= numRelationships <= 5 * 10^4`
Sample Cases
Example 1Sample Case
Input: 3 3
0 1
1 2
2 0
Output: true
Example 2Sample Case
Input: 3 3
0 1
0 2
1 2
Output: false
Example 3Sample Case
Input: 2 0
1 2
0 1
3 3
Output: false
Example 4Sample Case
Input: 1 0
0 1
2 2
Output: false
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.