Aiman N.

asked • 04/11/21

Optimize my code by converting Recursion to Iteration or any other method

Question: Given the graph where vertices represent worksites and edges represent pairs of sites that must be able to communicate securely. what are the fewest worksites that can have the securely-monitoring nodes to guarantee that each pair has atleast one. 

My Solution:

n, m = map(int, input().split())
p = [0] * m
target = 2 ** m - 1

def solve(i, subset, size):if subset == target:
return size
if i == n:
return n + 1return min(solve(i + 1, subset, size),
solve(i + 1, subset | p[i], size + 1))

for i in range(m):
u, v = map(int, input().split())
p[u] += 2 ** i
p[v] += 2 ** i

print(solve(0, 0, 0))

1 Expert Answer


Still looking for help? Get the right answer, fast.

Ask a question for free

Get a free answer to a quick problem.
Most questions answered within 4 hours.


Find an Online Tutor Now

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.