Solução de Frederico Bulhões
Para resolver esse problema devemos transforma-lo em um problema de grafos, onde cada aluno é um vértice, e uma amizade uma aresta.
Assim podemos ver que em cada componente conexa teremos obrigatoriament um grupo de amigos. Como queremos maximizar o número de grupos, devemos então contar o número de componentes conexas do grafo.
Para fazer isso podemos usar uma DFS, algoritmo básico de grafos e marcar os vértices visitados.
Código para melhor entendimento:
https://gist.github.com/fredbr/837c0412ae97c74419983f0a8d422cdf
Deixe um comentário