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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/example-cut-and-reconnect

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

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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/example-cut-and-reconnect

Repovive

Example: Cut and Reconnect - Link-Cut Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Example: Cut and Reconnect

Dynamic modification

Starting tree: 1-2-4, 1-3, 2-5

cut(2)       // Remove edge 2-1
// Now: tree1 = {1, 3}, tree2 = {2, 4, 5}

connected(1, 4)  // false

link(4, 3)   // Connect 4 to 3
// Now: tree = {1, 3, 4, 2, 5}
//        1
//        |
//        3
//        |
//        4
//        |
//        2
//        |
//        5

connected(1, 5)  // true
pathQuery(1, 5)  // path: 1-3-4-2-5

Link-Cut trees handle arbitrary sequences of link/cut operations.