Can anyone give me an idea how to solve this problem ? Tour de Byteotia Thanks in advance!

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

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

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

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

4 | rng_58 | 185 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 168 |

Can anyone give me an idea how to solve this problem ? Tour de Byteotia Thanks in advance!

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/15/2021 15:25:49 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by saba_tavdgiridze (previous revision, new revision, compare).Am I right or it is enough to find any spanning tree and delete other edges?

Apart from that, POIs have editorials. Try searching oi.edu.pl website

You're wrong since the graph is not necessarily connected, hence it can have no spanning tree.

By the way, even if the input graph always had a spanning tree, the solution would be still wrong.

Simply consider a clique, where you would add

N- 1 edges and at least is possible.Let's try to add the maximum amount of edges so that no cycle passes through vertices 1..K.

You can first of all add all "safe" edges (x; y) — those which have x>K and y>K.

After that, iterate through the others, and add an edge only in case it won't form a cycle (this can be checked with the help of DSU).

After we're done, the answer is formed by the edges we didn't add.