克魯斯卡爾重構樹

Kruskal重構樹

Kruskal重構樹，和Kruskal算法的思想差不多，就是在這個過程中建出一個有着非常優秀的性質的資料結構，這是一個非常少見和小衆的算法，但是如果碰到了合适的題目，就會展現出其優越性。

先将邊權排序（排序的方式決定了這顆重構樹的性質），我們把邊排完序之後依次周遊每條邊，如果這條邊兩端的\(u,v\)不在同一并查集内，那麼就建立一個節點\(node\)，我們設\(u,v\)兩點在并查集中的根分别為\(root_u,root_v\)，那麼我們連接配接\(node,root_u\)和\(node,root_v\)，然後用并查集更新\(root_u,root_v\)的\(father\)都更新為\(node\)，最後把這個點的點權相應的記錄為這條邊的邊權，一直這樣不斷的連邊，那麼我們就建出來了一顆Kruskal重構樹。