Solução Gincana - Semana 2

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: