what will happen if i run kruskal algorithm on disconected graph?? Actual problem is given n disconnected undirected graphs find kth largest value of mst of all graphs

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

10 | antontrygubO_o | 172 |

what will happen if i run kruskal algorithm on disconected graph?? Actual problem is given n disconnected undirected graphs find kth largest value of mst of all graphs

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2021 10:07:12 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

For the first part, running Kruskal on a disconnected graph would end up finding MSTs for the individual connected components until you eventually run out of edges

.

Reason :1. You've sorted all the edges.

2. An edge Ei has to belong to any of the m(say) connected components that you have in the graph. Hence you're basically solving the problem for m graphs in one go, because since you've sorted the edges of the graph, and connected components are disjoint and have no shared edges, discarding any edge while traversing the sorted list of edges won't jeopardize MST formation of other connected components