Data Structures19 sections · 729 units
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.