I got here up with following subproblem whereas engaged on one other downside. Can somebody verify if its a acknowledged downside. I’ve spent months however could not make any progress.
Design an information construction that maintains a directed graph. A node with node_id=Zero is created by default, having no edges. The information-structure helps following queries:
Create() : Create a brand new node with node_id assigned from an auto-incrementing counter. Add a directed edge from node-Zero to this new node; return node_id of latest node.
Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there may be already an edge from x to y.
Delete(x, y) : Delete the directed edge from node-x to node-y and likewise delete all of the nodes (and their edges) of graph which aren’t reachable from node-0. return the listing of deleted edges and nodes.
All queries ought to work in amortized complexity O(log(N)), the place N is the variety of nodes within the graph on the time of question.
PS: Its not a homework downside (clearly).