Detect cycle in directed dependency graph

You are given a directed dependency graph representing services in a system.

• There are n services, labeled from 0 to n - 1.
• You are given a list of directed edges dependencies, where each element is a pair [a, b] meaning service a depends on service b (i.e., there is a directed edge a -> b).

Assume:

• 1 <= n <= 10^5
• 0 <= a, b < n
• There may be zero or more edges.

Task:

1. Implement a function that determines whether there is at least one cycle in this directed graph.

   • Return true if there is a cycle.
   • Return false otherwise.

2. Follow-up: Now you are given multiple dependency arrays instead of just one. Each array represents an additional list of edges on the same set of services. For example:

   • dependencies1, dependencies2, ..., dependenciesk

   Each dependenciesi is a list of [a, b] pairs as defined above. Treat the union of all these edges as a single directed graph and determine whether this combined graph contains any cycle.

Describe the approach, data structures, and algorithm you would use, and analyze the time and space complexity.

Detect a Cycle in a Directed Dependency Graph

You are given a directed dependency graph representing services in a system.

• There are n services, labeled from 0 to n - 1.
• You are given a list of directed edges dependencies, where each element is a pair [a, b] meaning service a depends on service b (a directed edge a -> b).

Task: Implement a function that determines whether the graph contains at least one cycle. Return true if there is a cycle, otherwise return false.

A cycle means a chain of dependencies that loops back on itself (e.g. a -> b -> c -> a), which would make the services impossible to start in a valid order. A self-dependency [a, a] counts as a cycle.

Function signature: solution(n, dependencies) where n is the number of services and dependencies is a list of [a, b] pairs.

Constraints:

• 1 <= n <= 10^5
• 0 <= a, b < n
• There may be zero or more edges.

Examples

Example 1

Input: (3, [[0, 1], [1, 2], [2, 0]])
Output: True

Explanation: 0 -> 1 -> 2 -> 0 forms a cycle.

Example 2

Input: (3, [[0, 1], [1, 2]])
Output: False

Explanation: A simple chain 0 -> 1 -> 2 has no cycle.

Hints

1. A directed graph has a cycle if and only if a DFS encounters a 'back edge' — an edge that points to a node currently on the DFS recursion stack.
2. Track three states per node: unvisited, currently-on-stack (gray), and fully-processed (black). Seeing a gray neighbor means a cycle.
3. Because n can be up to 10^5, prefer an explicit (iterative) stack over deep recursion to avoid stack-overflow on long chains.
4. Don't forget disconnected components: start a DFS from every node that is still unvisited.

Detect a Cycle in the Union of Multiple Dependency Arrays

Follow-up to the single-graph cycle detection problem.

Now, instead of a single list of edges, you are given multiple dependency arrays over the same n services: dependencies1, dependencies2, ..., dependenciesk. Each dependenciesi is a list of [a, b] pairs meaning service a depends on service b (a -> b).

Task: Treat the union of all edges across every array as one combined directed graph, and determine whether that combined graph contains any cycle. Return true if the union has a cycle, otherwise false.

The key insight is that no single array needs to contain a cycle on its own — the cycle can emerge only once the edges are merged (e.g. one array supplies a -> b and another supplies b -> a).

Function signature: solution(n, dependency_arrays) where dependency_arrays is a list of edge lists; each edge list is a list of [a, b] pairs.

Constraints:

• 1 <= n <= 10^5
• 0 <= a, b < n
• Each array may have zero or more edges; there may be zero or more arrays.

Examples

Example 1

Input: (3, [[[0, 1]], [[1, 2]], [[2, 0]]])
Output: True

Explanation: Three arrays each supply one edge; their union 0 -> 1 -> 2 -> 0 is a cycle.

Example 2

Input: (3, [[[0, 1]], [[1, 2]]])
Output: False

Explanation: Union is the chain 0 -> 1 -> 2, no cycle.

Hints

1. You do not need to detect a cycle per array. Merge every edge from every array into one shared adjacency list, then run a single cycle-detection pass.
2. Reuse the same 3-color DFS from the single-graph version — the only change is how you populate the adjacency list.
3. Watch for cycles that only appear after merging: array 1 gives a -> b and array 2 gives b -> a; neither alone has a cycle, the union does.
4. Total work is O(n + E) where E is the combined edge count; iterating over arrays first does not change the asymptotic cost.