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:
| #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; | |
| } |

Comente