推 fereshte:是Sollin 51(C)是說每次contract後點的個數至少少一半 02/12 21:58
→ onlyeric23:google到mlogn = = 02/12 22:33
推 llll5566:mlongm 當m<<n^2 可寫成mlogn 02/12 22:37
→ ai305428d:原來如此 有點頭緒了 感謝樓上幾位^^ 02/12 22:39
→ onlyeric23:每次抓當前所有邊 然後又至少扣一半 所以mlogm這樣嗎? 02/12 22:42
→ ai305428d:我也是這樣想的~ 02/12 22:43
→ ai305428d:每次至少少一半點 共logn iteration 02/12 22:45
→ ai305428d:每次iteration至多考慮m個邊 02/12 22:45