Ir para conteúdo
Fórum Script Brasil
  • 0

Gincana - Obi 2011( C )


CaioCarvalhaes

Pergunta

Estava tentando resolver este problema com grafos e não consegui resolver, se alguém puder ajudar utilizando grafos, eu ficaria muito grato ❤️

Problema:

Toda semana Juquinha tem aulas de ACM (Artes Cênicas e Musicais) no colégio em que estuda e, recentemente, sua professora anunciou que haverá uma gincana no nal do semestre. No entanto, os times devem ser formados o mais breve possível para que os alunos possam ensaiar.

Cada time é constituído de um ou mais alunos, e cada aluno tem que pertencer a exatamente um time. Além disso, os times não podem ser formados de qualquer maneira: se um aluno é amigo de outro, esses alunos devem estar no mesmo time. A professora então pediu para que os alunos a informassem das relações de amizade na sala de aula.

Os alunos então se numeraram de 1 até N e escreveram uma lista cujas linhas contém pares de números. Se dois alunos cujos números são i e j são amigos, haverá ao menos uma linha contendo i e j ou j e i na lista. Inversamente, se há uma linha contendo i e j na lista, então os alunos cujos números são i e j são amigos.

A professora então recolheu a lista e, na próxima aula, deverá decidir que times formar. Ela está pensando em formar o maior número possível de times e gostaria de saber quantos times ela formaria. Ajude então a professora escrevendo um programa que, dada a lista de amizades, determina qual o maior número de times que ela pode formar

Editado por CaioCarvalhaes
Link para o comentário
Compartilhar em outros sites

0 respostass a esta questão

Posts Recomendados

Até agora não há respostas para essa pergunta

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152k
    • Posts
      651,8k
×
×
  • Criar Novo...