Walk an Object Graph with gc.get_referents and a Stack

To report on memory, you first find which objects a starting object can reach. In this exercise you follow references with gc.get_referents, count the nodes you reach, and find the starting nodes that sit on a cycle.

The starter does all of that, but its reachable_ids calls itself once for every step it takes. The hidden tests use chains of 10,000 nodes, far past Python's limit of 1,000 nested calls, so the starter raises RecursionError on them.

What to write

Rewrite reachable_ids(start) without recursion:

• Return the id() of every object reachable from start through gc.get_referents, including start itself, as a set[int].
• Keep the objects still to visit on an explicit stack or queue, and the IDs you have seen in a set.
• Do not change the recursion limit.

You can keep the starter's solve, which builds the report from reachable_ids. If you write your own, it must follow the rules below, and it must follow references with gc.get_referents instead of reading the answer from the graph dictionary. Leave build unchanged.

The graph

build(graph, chain, chain_closes) turns the input into real Python lists. Each name in graph, as a key or as an edge target, becomes one list. A list holds the node lists it points at, so gc.get_referents(node) returns exactly its successors.

When chain is positive, build also creates the nodes c0 to c<chain-1>, each pointing at the next. If chain_closes is true, the last one also points back at c0. A chain name that also appears in graph is the same node, and build adds the chain's edge to that node's own edges.

The report

solve(graph, roots, chain, chain_closes) returns two fields. Every name in roots exists in the built graph.

• "reachable": how many distinct named nodes are reachable from any root, counting the roots themselves. A node reached from two roots counts once.
• "cyclic_roots": the sorted root names that can reach themselves by following one or more edges. Check every entry in roots, so a cyclic root listed twice appears twice.

For a → b → c → b with roots a, b and c, the result is:

{"reachable": 3, "cyclic_roots": ["b", "c"]}

a leads into the cycle, but nothing leads back to a, so it is not cyclic.

Edge cases

• A node that points at itself is a cycle with one edge.
• A node with no edges is reachable from itself, but it is not cyclic.
• An empty roots list gives {"reachable": 0, "cyclic_roots": []}.
• A repeated edge changes nothing.
• Track visited nodes by id(). Two nodes can hold equal contents and still be different lists, and a list cannot go in a set.
• Do not change the inputs or the built nodes.

The count is a number of nodes, not a memory size. Your solution must pass mypy --strict.