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 
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 
. 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 
, e se for, adicionaremos 
à resposta e, após checar todos os alunos, a imprimimos. Vamos ao código:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #define MAXN 1100 | |
| int n, m, resp; | |
| int pai[MAXN], peso[MAXN]; | |
| int find(int x){ //funcao do Union-Find | |
| if(pai[x]==x) return x; | |
| return pai[x]=find(pai[x]); | |
| } | |
| void join(int x, int y){ // funcao do Union-Find | |
| x=find(x); | |
| y=find(y); | |
| if(x==y) return; | |
| if(peso[x]>peso[y]) pai[y]=x; | |
| if(peso[x]<peso[y]) pai[x]=y; | |
| if(peso[x]==peso[y]){ | |
| pai[x]=y; | |
| peso[y]++; | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d", &n, &m); // leia os valores de n e m | |
| for(int i=1; i<=n; i++){ // estabeleca que todo mundo é líder de sua própria equipe, apenas consigo mesmo | |
| pai[i]=i; | |
| } | |
| for(int i=1; i<=m; i++){ // para cada uma das m linhas seguintes | |
| int a, b; | |
| scanf("%d %d", &a, &b); // leia os valores dos números dos amigos | |
| join(a, b); // coloque os dois na mesma equipe | |
| } | |
| for(int i=1; i<=n; i++) if(find(i)==i) resp++; // a quantidade de líderes de equipe será a quantidade equipes | |
| printf("%d\n", resp); // imprima a resposta | |
| return 0; | |
| } |