|
|
back to boardDELETED Edited by author 04.08.2018 20:55 Re: hint O(N * log(M)) solution Let following situation: 1<---w(20)-->2<----w(20)--->3<----w(20)--->4<--.........--->50---w(20)-->1 | | ---w(100)--------------------- Kruskal's algorithm: finds first cycle 1-->2-->3-->4....->50-->1 : total path length = 50*20=1000. If we stop there, so actual minimal cycle 2-->3-->4-->2 : total path length = 20+20+100 = 140 can't found. |
|
|