Solução Gincana – Semana 2

Solução por Rogério Júnior

Para resolver esse problema, usaremos um algorítimo chamado Union-Find, então se você ainda não o conhece,  clique aqui para ver a aula do Curso Noic de Informática sobre Union-Find.

É importante lembrar que, no Union-Find, quando usamos a função $$join(aluno_1, aluno_2)$$ para juntar dois alunos em uma mesma equipe, ele elege um dos alunos dessa equipe como “líder de equipe”. O líder da equipe da cada aluno pode ser encontrado chamando a função $$find(aluno)$$. Assim, se inicializamos cada aluno sozinho em sua própria equipe e formos juntando-as à medida que surgem as amizades, ao final da entrada teremos o menor número possível de equipes e o líder do time de cada aluno.

Como cada equipe só tem um líder, basta contar quantos líderes de equipe existem. Assim, para cada um dos alunos, checaremos se ele é um líder. Para isso, basta ver se ele é o líder de sua própria equipe $$(if(find(i)==i))$$, e se for, adicionaremos $$1$$ à resposta e, após checar todos os alunos, a imprimimos. Vamos ao código:

https://gist.github.com/rogerioagjr/1860bba29e9fcd4002be