Dynamic Graph Problem | Is it solvable ?
Difference between en5 and en6, changed 0 character(s)
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.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English saharshluthra 2020-05-14 13:23:18 0 (published)
en5 English saharshluthra 2020-05-14 13:22:55 1 Tiny change: 'aintains an directed ' -> 'aintains a directed ' (saved to drafts)
en4 English saharshluthra 2020-05-14 10:47:41 0 (published)
en3 English saharshluthra 2020-05-14 10:45:22 2 Tiny change: 'ulty: Hard++\n\nDesign' -> 'ulty: Hard\n\nDesign'
en2 English saharshluthra 2020-05-14 10:45:06 2 Tiny change: ': Hard++\nDesign a' -> ': Hard++\n\nDesign a'
en1 English saharshluthra 2020-05-14 10:44:23 998 Initial revision (saved to drafts)