The solution above works even if your graph has cycles. Of course if you know that it doesn't you can just build the graph with unique_ptrs.

It works with cycles, as long as you can know exactly when you want to remove something from the graph (as opposed to having it be removed when no longer referenced). Reference counting works fine that way too, though. It's a bit more work, but you just dive into the structure and manually remove references which breaks any cycles it may be involved in.