Reference counting frees objects immediately but has a fundamental blind spot: an unreachable CYCLE (two or more objects that only reference each other) never hits a refcount of zero, so it leaks forever (see the Reference-Counting GC exercise's last test). Mark-and-sweep takes a different approach that handles this correctly: periodically walk the whole object graph from a known set of roots, mark everything reachable, and free everything that wasn't reached -- a cycle with no path back to any root gets swept just like anything else unreachable.

Objects are a dict of id -> object, where each object has a .refs list of other ids it points to.

Implement:

• mark(roots, objects) -- graph traversal (BFS or DFS, either is fine) starting from roots, returning the SET of ids reachable by following .refs edges (roots themselves count as reachable).
• sweep(objects, reachable) -- remove (from objects, IN PLACE) every id NOT in reachable. Return the list of freed ids.

Example

objects = {"a": Obj([]), "b": Obj([])}   # b unreachable from any root
reachable = mark(["a"], objects)          # -> {"a"}
sweep(objects, reachable)                 # -> ["b"], and objects is now {"a": ...}

Constraints

• mark must not infinite-loop on a cycle -- track visited ids and never revisit one.
• sweep mutates objects in place (via del), it doesn't return a new dict.

Real-world grounding

• CPython's cycle-detecting collector, which runs mark-and-sweep-style logic specifically to catch what refcounting alone can't: Modules/gcmodule.c
• Go's garbage collector (concurrent mark-and-sweep, tricolor marking): src/runtime/mgc.go

Production mark-and-sweep collectors add a lot on top of this: running concurrently with the program (tricky, since the graph can change mid-scan), generational collection (young objects are scanned far more often than old ones, since most objects die young), and incremental/tricolor marking to bound pause times -- but "traverse from roots, free what wasn't reached" is the algorithm underneath all of them.