Hello, how can Kruskal's algorithm be modified to run in O(n^2) time in a dense graph of n nodes??
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Name |
---|
This seems well explained and it has cpp code.
Why do you need Kruskal for such a task? Prim have your desired complexity, and is not much harder to implement compare to Kruskal.
I am thinking that since Kruskal is usually faster to implement from scratch compared to Prim, the OP was hoping for an easy modification to Kruskal to achieve O(N^2) time complexity on dense graphs so that he could use it in more contexts during contests.
What does OP mean?
Original poster
It's the same as O(V^2 + E) dijkstra, just linearly search for smallest cost vertex that hasn't been visited yet.
Edit: I meant prim