graph centroid vertex @ equal distance or @ distance less or equal (n/2) n size of connected components connected through vertex?! [needs correction?!]
here's problem @ codeforces asks find whether each vertex centroid, after removing , replacing 1 edge @ time.
i need refine pseudocode / algorithm.
loop vertices: loop edges: position each edge in every empty edge position between 2 unconnected nodes count size of each connected component (*1). if sizes less or equal n/2, return true
the problem algorithm run in @ least o(n*m^2)). it's not acceptable.
i looked answers, couldn't come high level abstraction of algorithm used others. please me understand how these solutions work?
(*1) dfs loop
i try describe not complex algorithm solving problem in linear time, future references see code (it have comments).
the main idea can root tree t @ arbitrary vertex , traverse it, each vertex v can this:
- cut subtree v t.
- find heaviest vertex h having size <= n/2 (h can in of t or subtree v).
- move subtree h become child of subtree v.
- re root t v , find if heaviest vertex have size <= n/2
the previous algorithm can implemented linear time complexity, issue have lot of cases handle.
a better idea find centroid c of t , root t @ vertex c.
having vertex c root of t useful because guarantee every descendant of c have size <= n/2.
when traversing tree can avoid check heaviest vertex down tree up, every time visit child w, can pass heaviest size (being <= n/2) if re root t @ w.
try understand explained, let me know if not clear.
Comments
Post a Comment