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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/dynamic-connectivity-solution

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

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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/dynamic-connectivity-solution

Repovive

Dynamic Connectivity Solution - Link-Cut Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Dynamic Connectivity Solution

Link-Cut tree approach

class DynamicForest:
    nodes: array of Node

    function link(u, v)
        makeRoot(nodes[u])
        nodes[u].pathParent := nodes[v]

    function cut(u, v)
        makeRoot(nodes[u])
        access(nodes[v])
        // u is left child of v now
        nodes[v].left.parent := null
        nodes[v].left := null

    function connected(u, v)
        return findRoot(nodes[u]) = findRoot(nodes[v])

All operations $O(\log n)$ amortized.

For competitive programming, implement the full splay tree with access/makeRoot carefully. Off-by-one errors in rotation and parent updates are common.