Maximize tokens from nested crates
Overview
This question evaluates proficiency with graph-based algorithms, state management, and data structure selection for handling dependencies, cycles, duplicates, and dynamic discovery in resource-collection scenarios.
You are given n crates, each either locked or unlocked. Each crate i contains: an integer tokens[i]; a list of keys that can unlock other crates; and a list of new crates that become available when you open it. You start with a set of initial crates you can access (they may be locked). You may repeatedly: open any accessible unlocked crate, collect its tokens, add any newly found crates to your accessible set, and use any keys found to unlock crates. Return the maximum total tokens you can collect. Design an algorithm with near O(n + total_edges) time, specify data structures, and correctly handle cycles, duplicates, and crates discovered before their keys.