22.2-6
There are two types of professional wrestlers: "good guys" and "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 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.

Resolução
A etapa inicial deste problema é criar um grafo G em que cada um dos n lutares profissionais representa um vértice e cada uma das r rivalidades uma aresta. O tipo de cada lutador u é armazenado em tipo[u] e pode ser BOM, MAU, ou DESCONHECIDO, sendo este último para vértices ainda não visitados. O algoritmo BUSCA-ALTERNADA é uma versão modificada do algoritmo BFS específico para este problema. Ele gera um erro se encontra uma rivalidade entre lutadores do mesmo tipo (BOM ou MAL, pois u não pode ser DESCONHECIDO) e atualiza os tipos dos vértices do componente conexo se o algoritmo chega ao fim sem erro.

BUSCA-ALTERNADA(G, s)
1   tipo[s] ← BOM
2   Q ← ∅
3   ENQUEUE(Q, s)
4   while Q ≠ ∅ do 
5       u ← DEQUEUE(Q)
6           for cada v ∈ Adj[u] do 
7               if tipo[v] = tipo[u] then erro!
8               else 
9                   if tipo[v] = DESCONHECIDO then
10                      if tipo[u] = BOM then tipo[v] ← MAU
11                      else tipo[v] ← BOM
12                      ENQUEUE(Q, v)
    

Como o grafo pode ser desconexo, o algoritmo LUTADORES-PROFISSIONAIS certifica que todos os vétices foram testados. Ele utiliza BUSCA_ALTERNADA e, se ocorrer um erro, repassa a quem o chamou e termina. Ao final, se todos os vértices foram testados e não houve erro, os tipos de todos os lutadores profissionais estão atualizados.

LUTADORES-PROFISSIONAIS(G)
1   for cada vértice u ∈ V[G] do
2       if tipo[u] = DESCONHECIDO then
3           BUSCA_ALTERNADA(G, u)
    

A complexidade de BUSCA-ALTERNADA, é O(n' + r') para um componente conexo de G, sendo que n' e r' são respectivamente o número de vértices e arestas deste componente. LUTADORES-PROFISSIONAIS é O(n), mas ele só chama BUSCA-ALTERNADA uma vez para cada componente conexo, sendo que, no pior caso, a soma de todos os n' será igual a n e todos os r', igual a r. Portanto, a complexidade da solução é O(n + r).

Autor
Milton Aparecido Soares Junior