AULA 29:
-------
O problema da identificacao de uma celebridade.

Rita e' uma colunista e esta' fazendo a cobertura de uma festa.  Seu trabalho
e' identificar uma celebridade, caso ela exista. Uma celebridade e' uma pessoa
que e' conhecida por todas as demais pessoas da festa, mas que nao conhece
ninguem.   Rita  faz a seguinte pergunta aos convidados: "voce conhece aquela
pessoa ali?".  Considere que todas as pessoas vao responder a pergunta de
forma sincera. Escreva um programa que ajuda a tarefa de Rita identificar
uma celebridade da festa.

Uma pessoa P é identificada como uma celebridade em uma festa se:
 C1: todos conhecem P
 C2: nao conhece ninguem

1) representacao do fato de Pi conhecer Pj em uma matriz:
  m[i,j] = 0 se Pi nao conhece Pj
  m[i,j] = 1 de Pi conhece Pj

Escrever um procedimento que leia uma sequencia de pares e preencher a matriz. Não esqueça de inicializar a matriz com zeros.
Exemplo (considerando 5 pessoas):
  3 4
  5 1
  5 4
  2 1
  2 4
  1 4

  matriz   0 0 0 1 0
           1 0 0 1 0
	   0 0 0 1 0
	   0 0 0 0 0
	   1 0 0 1 0

-----------------------------------
Solucao 1: Forca Bruta
Para cada pessoa na festa, verificar se as condicoes C1 e C2 definidas acima sao satisfeitas.  Se existirem N pessoas na festa este algoritmo tem complexidade N^2, uma vez que para cada pessoa ela tem que verificar as condicoes com a relacao a todas as demais. 

----------------------------------
Solucao 2: Solucao usando o TAD Pilha

1) Escrever um procedimento que inicializa uma pilha com todas as pessoas.  No exemplo anterior, a pilha deve conter os numeros de 1 a 5.

2) Escrever uma funcao que retorna uma possivel celebridade a partir da pilha de pessoas.  A ideia e' que seja removida da pilha as pessoas que nao podem ser celebridades da seguinte forma:
     remova da pilha uma pessoa p1
     remova da pilha uma pessoa p2
     se p1 conhece p2 entao
        - p1 nao pode ser uma celebridade, mas p2 pode
	- assim, insira p2 novamente na pilha
     se p1 nao conhece p2 entao
        - p1 pode ser uma celebridade, mas p2 nao
	- assim, insira p1 novamente na pilha

Este processo deve ser repetido ate' que apenas 1 pessoa sobre na pilha.  Esta e' a unica pessoa que pode ser uma celebridade e deve ser retornada pela funcao.

3) Escrever uma funcao que verifique se a pessoa retornada pela funcao anterior e' realmente uma celebridade verificando a coluna e linha correspondente a pessoa na matriz.

-------------------------------------
Solucao 3: usando o TAD Conjunto
- igual a solucao anterior, utilizando o TAD Conjunto
- Pergunta: qual solucao e' melhor?

-------------------------------------
Solucao 4: usando 2 indices (p1, p2)

   1   2   3   4   5
  p1               p2

Utiliza a mesma ideia da Solucao 2, mas considerando as pessoas dos indices ini e fim.  Se p1 conhece p2, incrementa p1 (ou seja, p1 nao pode ser celebridade).