Implement a C++ Program for:

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.

Solution: We can represent the rivalries as a graph, G = (V, E) where the vertices are the wrestlers, and the edges are the rivalries. Therefore, |V| = n, and |E| = r.

Algorithm:

1. Discard all vertices with degree 0. These are wrestlers who have no rivalries. We are not concerned with them.

2. Separate all connected components of the remaining graph. Process each component individually in the following steps.

3. Let C = (Vc, Ec) be the connected component. Choose one vertex r at random from Vc. Let r be classified as babyface.

4. We use BFS to traverse C starting from root. All vertices with odd path lengths from the root are labeled as Heels and all the vertices with even path lengths from the root are labeled babyfaces.

5. Next we check every edge in Ec. If the edge is between two vertices whose path lengths from root are both even or both odd, then it means that we have established a rivalry between two babyfaces or two heels. If this is the case, we return FALSE i.e it is not possible to partition the wrestlers.

6. We run BFS for every such connected component of the graph. If we find every edge in every connected component to join a babyface and a heel, then we have successfully partitioned the wrestlers