Well, you can use weak pointers appropriately in a safe setting. It's not fun though. Alternately, you can use a layer of indirection, such as throwing all your graph nodes in a big vector and having them use indices to refer to one another.

So I would perhaps revise that statement to "easy cyclic data structures, memory safety, memory management without tracing, pick two".