Maximum number of Connected Component

Revision en1, by prodipdatta7, 2019-04-05 11:11:44

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...

Tags #graphs, biconnected-components, #bridges

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English prodipdatta7 2019-04-05 11:12:50 4 Tiny change: '======= \nYou are ' -> '======= \n\nYou are '
en1 English prodipdatta7 2019-04-05 11:11:44 845 Initial revision (published)