Hot answers tagged

2

There are two ways this problem can be solved. I really like these solutions. Square Root Decomposition Keep a set of at most O(sqrtN) "active nodes". When you have a query of type 2, just loop through all these active nodes and add the distance between each one to the queried node. When you have a query of type 1, add the new node to the set if ...


1

Yes, the greedy algorithm (you described) works. Given a directed graph, call a subset of its vertices "a 3-separated set" if there isn't a path of length less than 3 between any pair of vertices among them. Call a 3-separated set a 3-separated-max set if it contains the maximum number of vertices. The problem is to find a 3-separated-max set in a ...


1

You want to prove a false statement. Its possible that T -{a} + {b} is not spanning tree. Consider the below example Lets say T1 is- 1 / \ 2 3 / / 5 4 / 6 Lets say T2 is- 1 \ 2 3 /|\ / 5 6 4 both are spanning tree but if we replace edge 1-2 in T1 with edge 2-6 in T2 then it will not be ...


Only top voted, non community-wiki answers of a minimum length are eligible