So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional 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 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."

This was on a quiz I took today. So I assumed there was some sort of trait that we would be able to use to determine whether a wrestler was a heel or babyface whenever we went over them. What I thought would work would be to create an undirected graph containing each wrestler as a connected node. The order nor do the relationships matter. Then I would Breadth-first-search through all of them. Instead of just one queue, though, I would use two. After being visited, the node would either be placed in the babyface queue or the heel queue. When both queues weren't completely empty, then I would dequeue each and pair one and one together, before going back and continuing the search.

Would this work as a solution or no?


Another way to state this problem is:

Given an undirected graph, determine whether it can be 2-colored in $O(V+E)$. Equivalently, determine whether it is bipartite.

The simplest solution is to use what my algorithms professor called WFS: Whatever-First Search. That is, like BFS or DFS, except you don't care what order you traverse in. (You can replace "bag" with "queue" to get BFS, or "stack" to get DFS, if you like.)

while there are uncolored nodes:
    pick an arbitrary uncolored node
    color it red
    put all its neighbors in a "bag" (arbitrary container data type)
    while the bag is not empty:
        remove a node from the bag
        if it has neighbors of both colors, RETURN FALSE
        color it the opposite of its neighbors
        add its uncolored neighbors to the bag

Here, "coloring a node red" = marking it as a babyface, and "coloring a node blue" = marking it as a heel. Edges are rivalries, nodes are wrestlers.

This aligns with the usual intuition for this problem: "start with some arbitrary node, color it red, color all its neighbors blue, color all their neighbors red…"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.