Hi,↵
↵
I came with this subproblem while working on something else. Can someone help me understand if it's solvable problem ?↵
↵
-----------------------↵
↵
Difficulty: Hard↵
↵
Design a data structure that maintains a directed graph. A node with node_id=0 is created by default, having no edges. The data-structure supports following queries:↵
↵
1. Create() : Create a new node, with node_id assigned from an auto-incrementing counter. Add a directed edge from node-0 to this new node; return node_id of new node.↵
↵
2. Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there is already an edge from x to y.↵
↵
3. Delete(x, y) : Delete the directed edge from node-x to node-y, and also delete all the nodes (and their edges) of graph which are not reachable from node-0. return the list of deleted edges and nodes.↵
↵
All APIs should work in amortized complexity O(log(N)) , where N is the number of nodes in the graph at the time of query.↵
↵
I came with this subproblem while working on something else. Can someone help me understand if it's solvable problem ?↵
↵
-----------------------↵
↵
Difficulty: Hard↵
↵
Design a data structure that maintains a directed graph. A node with node_id=0 is created by default, having no edges. The data-structure supports following queries:↵
↵
1. Create() : Create a new node, with node_id assigned from an auto-incrementing counter. Add a directed edge from node-0 to this new node; return node_id of new node.↵
↵
2. Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there is already an edge from x to y.↵
↵
3. Delete(x, y) : Delete the directed edge from node-x to node-y, and also delete all the nodes (and their edges) of graph which are not reachable from node-0. return the list of deleted edges and nodes.↵
↵
All APIs should work in amortized complexity O(log(N)) , where N is the number of nodes in the graph at the time of query.↵
