There are two types of wrestlers: \"good guys\" and \"bad guys\". Between any pa
ID: 3625815 • Letter: T
Question
There are two types of wrestlers: "good guys" and "bad guys". Between any pair of wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n+r)-time algorithm that determines whether it is possible to disignate some of the wrestlers as "good guys" and the remainder as "bad guys" such that each rivalry is between a "good guy" and a "bad guy". If it is possible to perform such a designation, your algorithm should produce it.
Please include correctness and analysis...
Explanation / Answer
// Algorithm for determines whether it is possible to designate some of the wrestlers.
// Input: An array W of distinct names of wrestlers and an array R of distinct pairs of rivalries.
// Output: Print whether wrestlers as babyfaces (good guys) and heels (bad guys).
1. Create a graph where the vertices are the wrestlers and the edges are the rivalries between wrestlers.
3.After we finish BFS we examine if there is any vertex that has a neighbor at the same level of the tree.If so there is no possible designation otherwise we print the vertices as marked by the algorithm.
4.Suppose all the wrestlers in the even leels will be the good one's and all the wrestlers in the odd levels will be the bad one's.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.