prodipdatta7's blog

By prodipdatta7, history, 5 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prodipdatta7 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

The problem is equivalent to the k-cut problems, which is NP. The reduction is the following:

Assume we can solve your problem. Let's solve it for every possible $$$k$$$. If answer for given $$$k$$$ is $$$f(k)$$$ we can easily see that $$$k$$$ is the answer for the $$$f(k)$$$-cut problem. But it is NP => your problem is also NP.