紀錄一下學一些新的演算法的過程
問題：
給定一堆帶權無向連通圖，如何快速求出其中的第二小生成樹？
窮舉生成樹？
對所有邊，先標記其為樹邊再直接搜生成樹，紀錄第二小...
O(M) 窮舉 * O(M logM) = O(M^2 logM)
看起來爆了
想想...
若拔掉MST上的一個邊，再加上另一個 non-tree edge，應該可能是第二小的吧！？
先求最小生成樹？
Kruskal's： O(E logE)
拔邊+窮舉 non-tree edge 找第二小？
O(E logE) + O(V - 1) 拔邊 * O(E) 窮舉剩下邊 = O(VE)
看起來還是爆了
再想想...
如果今天要加上一個 non-tree edge ，一定會成為一個環。
那拔掉環上的最重邊不就好了嗎？
但如何找到最重邊...
窮舉環上邊 O(E) 一樣會爆，那就用 jumping pointers，O(log V) 查找？
O(E logE) + O(V logV) 建表 + O(E) 窮舉 non-tree edges * O(log V) 找 lca 和環上最重邊
= O(E logE)
看起來好多了！
找 MST -> DFS轉成有根樹 -> 窮舉邊 -> 若邊在樹上則直接返回，否則找 lca
達人
