Here is the centroid decomposition implementation:
function centroidDecomposition(n, adj):
removed = array of size n, all false
centroidParent = array of size n, all -1
function getSubtreeSize(u, parent):
size[u] = 1
for v in adj[u]:
if v != parent and not removed[v]:
size[u] = size[u] + getSubtreeSize(v, u)
return size[u]
function getCentroid(u, parent, treeSize):
for v in adj[u]:
if v != parent and not removed[v]:
if size[v] > treeSize / 2:
return getCentroid(v, u, treeSize)
return u
function decompose(u, parent):
treeSize = getSubtreeSize(u, -1)
centroid = getCentroid(u, -1, treeSize)
centroidParent[centroid] = parent
removed[centroid] = true
for v in adj[centroid]:
if not removed[v]:
decompose(v, centroid)
decompose(0, -1)
return centroidParent
Time: . Space: .