Algorithms: How can we optimize the relevant problem for the subset?


Problem: Given a set S of integers from 1 to n, and m pairs of numbers A_i and B_i, (A_i is not equal to B_i). Find the smallest integer k so that each subset has exactly k elements of S that contain at least one of the m pairs of numbers given or, in other words, each subset with k elements of S must contain at least one pair A_i and B_i.

Entry:

  • The first line contains two numbers: n and m (1 <= n <= 80.1 <= m <= 100)

  • The following is m straight lines, each line has A_i and B_i

  • Note: Let l be the number of pairs i, j (i, j <= m, i! = J) so that A_i = B_j then l <= 5.

Exit: That is what we need.

For example:

4 4

1 3

2 4

1 4

-> Answer: 3

Explenation: With k = 3. Clearly, {1,2,3}, {1,2,4}, {2,3,4} has at least one pair of m pairs.

This is my attempt: my idea is to use bitmask to show all subsets of S. With each i
(i from 0 to (1<. I check if there are any pairs of m satisfied pairs i. If you don't have any satin pairs, when it implies

This is my code: (Mycode)(1)

But, I only have a true 17/20 test case. So, I want to post it here to answer that how can we optimize this problem! (In my solution, I still haven't used the problem note)