題目目錄Redundant Connection

每加一條邊就問兩端的老大是誰：老大不同就合併，老大相同代表這條邊造成環。

TIME O(n · α(n))空間 O(n)：parent 陣列

01 / 圖與 parent 森林INITIALIZE

邊—

[a, b]—

ra—

rb—

圖邊依序加入；顏色 = 所屬的組

parent 森林箭頭指向 parent；最上面是老大

parent

find

edges

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：為什麼「老大相同」就代表有環？

同一組的點，早就有路互通。

parent[x] 是 x 的上司。一路往上找到上司是自己的點，就是這一組的老大（root）。同一組的點老大相同。

每加一條邊 a — b：如果 a、b 老大不同，代表兩組原本不連通，把其中一個老大掛到另一個老大底下就合併了。

如果老大相同，代表 a 和 b 之間本來就有一條路，再加這條邊就繞成一個環，所以它是多餘的邊。

路徑壓縮：find 回傳的路上，把每個點的 parent 直接改成老大，樹會被壓平，之後再找就很快。平均每次操作接近 O(1)。