Hello Codeforces!↵
↵
Recently I have solved some problem with Articulation Bridge. Then I have come up with a problem that can be solved using Bridge but till now I can't figure out an appropriate solution.↵
↵
Problem Description↵
↵
================== ↵
↵
You are given a connected undirected graph of n nodes and m edges and an integer k.↵
↵
Now the question is, What is the maximum number of connected components you can create by deleting exactly k edges (k <= m)? ↵
↵
Addition: How to solve the problem if there are Q queries of k? ↵
↵
time limit: 1s for a single case, 2s for the query.↵
memory limit: 512 MB. ↵
↵
Note: if k <= number_of_bridges in the graph, then it is easy to prove that the answer will be k + 1.↵
↵
Please give me some hints/resources that how can I come up with an efficient solution...
↵
Recently I have solved some problem with Articulation Bridge. Then I have come up with a problem that can be solved using Bridge but till now I can't figure out an appropriate solution.↵
↵
Problem Description↵
↵
================== ↵
↵
You are given a connected undirected graph of n nodes and m edges and an integer k.↵
↵
Now the question is, What is the maximum number of connected components you can create by deleting exactly k edges (k <= m)? ↵
↵
Addition: How to solve the problem if there are Q queries of k? ↵
↵
time limit: 1s for a single case, 2s for the query.↵
memory limit: 512 MB. ↵
↵
Note: if k <= number_of_bridges in the graph, then it is easy to prove that the answer will be k + 1.↵
↵
Please give me some hints/resources that how can I come up with an efficient solution...
