Babyfaces vs. Heels. There are two types of professional wrestlers: “babyfaces”
ID: 3766913 • Letter: B
Question
Babyfaces vs. Heels. There are two types of professional wrestlers: “babyfaces” (the good guys) and “heels” (the bad guys). Between any pair of wrestlers there may or may not be a rivalry. Suppose there are n wrestlers and we have a list of r pairs of wrestlers for which there are rivalries.
(a) Give an algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
(b) What is the worst-case run time of your algorithm?
Explanation / Answer
Represent the problem as a graph, where each vertex represents a wrestler and each edge represents a rivalry. The graph will have n vertices and r edges. Perform as many BFS’s as are needed to visit all n vertices. Assign the first wrestler to be a good guy and then assign all its immediate neighbors to be bad guys, and so on. If a wrestler is assigned to be a good guy (or bad guy), but one of its neighbors has already been assigned to be a good guy (or bad guy), report that a desired designation is not possible. The solution has BFS’s complexity, which is O(n + r).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.