Let’s say you’re going to invite some people to a party. You’re considering n friends, but you know that they will only have a good time if each of them knows at least k others at the party. (Assume that if A knows B, then B automatically knows A.) Solve your problem by designing an algorithm for finding the largest possible subset of your friends where everyone knows at least k of the others, if such a subset exists. To help you get started I’ve made a graph of “my friends”: G={'Rachel':['Ross','Monica'], 'Ross':['Rachel','Monica'], 'Monica':['Rachel','Ross'], 'Jon Snow':['Daenerys','Sansa','Arya'], 'Daenerys':['Jon Snow','Sansa','Arya','Khal Drogo'], 'Sansa':['Jon Snow','Daenerys','Arya'], 'Arya':['Jon Snow','Daenerys','Sansa'], 'Khal Drogo':['Daenerys'], 'Cersei':['Jaime'], 'Jaime':['Cersei'], 'Bart':['Milhouse'], 'Milhouse':['Bart','Lisa'], 'Lisa':['Milhouse'], 'Leslie':['Ron','Ann','Ben'], 'Ron':['Leslie'], 'Ben':['Leslie','Ann'], 'Ann':['Leslie','Ben'],}
Python
Let’s say you’re going to invite some people to a party. You’re considering n friends, but you know
that they will only have a good time if each of them knows at least k others at the party. (Assume that if A knows B, then B automatically knows A.) Solve your problem by designing an algorithm for finding the largest possible subset of your friends where everyone knows at least k of the others, if such a subset exists.
To help you get started I’ve made a graph of “my friends”:
G={'Rachel':['Ross','Monica'], 'Ross':['Rachel','Monica'], 'Monica':['Rachel','Ross'], 'Jon Snow':['Daenerys','Sansa','Arya'], 'Daenerys':['Jon Snow','Sansa','Arya','Khal Drogo'], 'Sansa':['Jon Snow','Daenerys','Arya'], 'Arya':['Jon Snow','Daenerys','Sansa'], 'Khal Drogo':['Daenerys'], 'Cersei':['Jaime'], 'Jaime':['Cersei'], 'Bart':['Milhouse'], 'Milhouse':['Bart','Lisa'], 'Lisa':['Milhouse'], 'Leslie':['Ron','Ann','Ben'], 'Ron':['Leslie'], 'Ben':['Leslie','Ann'], 'Ann':['Leslie','Ben'],}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
