Design a reusable graph traversal that processes reachable nodes concurrently, visits every node at most once, and terminates cleanly even when the graph contains cycles.

Implement the ParallelGraphTraversal class:

graph[node] contains the outgoing neighbors of node. The graph is directed and may contain cycles, self-loops, duplicate edges, and disconnected components.

Call visitNode(node) exactly once immediately before expanding that node's outgoing edges. Callbacks for different nodes may overlap when maxThreads > 1, but no more than maxThreads callbacks may be active simultaneously.

Traversal order is intentionally unspecified. A valid implementation may resemble breadth-first search, depth-first search, or another work-queue traversal, provided that it satisfies the reachability, exactly-once, concurrency, and termination requirements.

The callback is an observation hook used by the judge. It returns normally and does not access or modify graph. Do not modify or reorder any adjacency list.

The same traversal may be reused for multiple completed calls, and different instances must be independent. The judge does not call traverse concurrently on the same instance.

The judge supplies the graph and callback. Standard concurrency, callback, collection, lock, and thread APIs are preloaded, so you do not need import, include, package, or using statements.

Example 1:

Input:

Output:

Explanation: Node 4 is disconnected from the start node. The cycle from 2 back to 0 does not cause another visit.

Example 2:

Input:

Output:

Explanation: Self-loops and duplicate edges are ignored after their destination has been discovered.

Constraints

Starter Code

Parallel traversal has two separate coordination problems.

First, several workers may discover the same neighbor through different edges. The check and mark of the visited state must be one atomic operation; checking first and marking later can enqueue the same node multiple times.

Second, an empty frontier does not necessarily mean the traversal is finished. A worker may currently be expanding a node and may add more work. Workers need a termination condition that distinguishes temporary emptiness from globally completed work.

Maintain these shared values under one lock:

Initially, mark start, place it in the frontier, and set pending = 1.

The key invariant is:

When a worker discovers a new neighbor, it marks the neighbor, enqueues it, and increments pending while holding the same lock. After finishing one node, it decrements pending.

Therefore, pending == 0 proves that the frontier is empty and no active worker can create more work. That is the safe global termination condition.

Each participant repeatedly:

The callback must run outside the state lock. Otherwise, one slow callback would serialize every worker and prevent observable parallel progress.

Use min(maxThreads, graph.length) participants. The calling thread performs work too, so create at most one fewer additional workers.

The start node is marked before it enters the frontier. Every other node is enqueued only inside the atomic check-and-mark section. Thus, no reachable node can be enqueued or visited more than once.

Whenever a processed node has an unvisited outgoing neighbor, that neighbor is marked and enqueued. Repeating this argument along every path from start shows that every reachable node is eventually visited. Nodes without a path from start are never discovered.

Workers exit only when pending == 0. By the invariant, no queued or active node remains at that point, so no future discovery is possible and traverse can safely return.

The number of participants is fixed at the start of the call, so callback overlap cannot exceed maxThreads. All traversal state is local to one call, which keeps reuse and separate instances independent.

Let V and E be the numbers of reachable nodes and examined outgoing edges.