#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-decomposition

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-decomposition

Repovive

Implementation - Decomposition - Heavy-Light Decomposition | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Decomposition

(Building chains)

Run a second DFS to assign chains and positions:

cur_pos := 0

function dfs_hld(v, par, c)
    chain[v] := c
    if new chain then
        head[v] := v
    else
        head[v] := head[par]
        pos[v] := cur_pos
        cur_pos := cur_pos + 1
        heavy := -1
        for u in adj[v]
            if u != par and (heavy = -1 or size[u] > size[heavy]) then
                heavy := u
                if heavy != -1 then
                    dfs_hld(heavy, v, c)
                    for u in adj[v]
                        if u != par and u != heavy then
                            dfs_hld(u, v, new_chain)

This assigns positions and chains in $O(n)$ time. Process the heavy child first to keep chains contiguous.

Space complexity is $O(n)$ for the data structures used.