Bart S. answered • 04/13/21

Programming major helping young people or adults start from zero.

This involves changing the space-time complexity of the program.

Aiman N.

asked • 04/11/21**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))

Follow
•
1

Add comment

More

Report

Bart S. answered • 04/13/21

Tutor

New to Wyzant
Programming major helping young people or adults start from zero.

This involves changing the space-time complexity of the program.

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.