Spitballing:

A neat technique for representing graph structures in an RC-only environment is to make every object in the graph share the same refcount. (As a conservative overapproximation of their actual lifetimes.)

Mayhaps this could be semi-automated? When a link is formed between such objects (based on whether their types are marked as "graph-y" or something, TBD), replace the refcount of one with an indirection to that of the other (& also add them). And ... this is basically union-find!