Social follow graph with point-in-time snapshots

Build an in-memory follow graph that can answer questions about its own past. Follows are directed: a following b says nothing about b following a.

Implement a SocialNetwork class:

• SocialNetwork() creates an empty graph.
• follow(follower: int, followee: int) -> None makes follower follow followee in the current working state. Following yourself, or following someone you already follow, does nothing.
• unfollow(follower: int, followee: int) -> None removes that follow from the working state. Removing a follow that does not exist does nothing.
• snapshot() -> int freezes the working state and returns its id. Ids start at 0 and go up by 1 with each call.
• is_following(follower: int, followee: int, snap_id: int) -> bool returns whether follower followed followee at the moment snapshot snap_id was taken. Changes made after that snapshot do not affect the answer. Raise an error for an id that has not been returned by snapshot().

Constraints

• Up to 10^5 users and 2 * 10^5 calls in total.
• Many snapshots may be taken with few or no changes between them, so copying the whole graph on each snapshot is too slow and uses too much memory.
• Aim for O(1) follow, unfollow and snapshot, and O(log n) is_following.

Example 1

g = SocialNetwork()
g.follow(10, 20)
g.follow(10, 30)
g.snapshot()            -> 0
g.unfollow(10, 20)
g.follow(20, 10)
g.snapshot()            -> 1
g.is_following(10, 20, 0) -> true
g.is_following(10, 20, 1) -> false
g.is_following(20, 10, 0) -> false
g.is_following(20, 10, 1) -> true

Example 2

g = SocialNetwork()
g.follow(4, 7)
g.unfollow(4, 7)
g.follow(4, 7)
g.snapshot()            -> 0
g.snapshot()            -> 1
g.unfollow(4, 7)
g.is_following(4, 7, 1) -> true   # the unfollow came after snapshot 1
g.is_following(7, 4, 1) -> false  # follows are directed

Be ready to extend the class: list a user's followees at a snapshot, then recommend accounts to follow based on the graph at a snapshot.