Como calcular a quantidade máxima de times em dupla?

[GustavoCarvalhaes]

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.

Entrada

A primeira linha da entrada contém dois inteiros N e M que representam, respectivamente, o número de alunos na turma e o número de linhas na lista. As próximas M linhas contêm a lista de amizades. Cada linha contém dois inteiros I e J separados por exatamente um espaço.

Saída

Seu programa deve imprimir uma linha contendo o número máximo de times que podem ser formados pela professora.

[DiF]

Caro usuário,

 

Seja bem-vindo ao Fórum do Clube do Hardware.

 

No intuito de servir como fonte de pesquisa no caso de instituições de ensino, informamos que incorrer no resolvimento por completo de questões relacionadas a disciplinas escolares de cursos técnicos e faculdades podem ser revistas e removidas pela Equipe de Moderação do Clube do Hardware.

 

Para sanar dúvidas sobre esse tipo de problema, por gentileza, publique o passo a passo do desenvolvimento da questão, projeto, monografia ou conteúdo em dúvida para que possamos analisar se a resposta está correta ou não, ou para que possa ser auxiliado com a dúvida no desenvolvimento do exercício.

 

Infelizmente, não há como resolver os trabalhos pelos usuários. O objetivo do Fórum do Clube do Hardware é auxiliar seus usuários a encontrar soluções para que possam sanar suas dúvidas, e não de trazer soluções prontas para seus usuários.. Além disso, copiar e colar respostas que não são de autoria própria do qualquer usuário é considerado plágio, o que é ilegal.

 

Esperamos que compreenda.

 

Atenciosamente,

Equipe Clube do Hardware