Solução Informática Intermediário - Semana 46

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:


//solucao de Davi Gabriel
#include <bits/stdc++.h>
#define MAXN 1010
using namespace std;
int mark[MAXN]; //Declaro o que será necessário
vector < int > vizinhos[MAXN];
void DFS(int x){ //Crio a DFS
mark[x] = 1;
for(int i = 0; i < vizinhos[x].size(); i++){
int f = vizinhos[x][i];
if(mark[f] == -1){
DFS(f);
}
}
}
int main() {
int n, m, ans = 0;
cin >> n >> m;
memset(mark, -1, sizeof(mark)); //Inicializo como se nenhum vertice fosse visitado
for(int i = 0; i < m; i++){
int p, q;
cin >> p >> q;
vizinhos[p].push_back(q); //Registro a aresta que liga os vértices p e q
vizinhos[q].push_back(p); //Ou seja, registro que são amigos
}
for(int i = 1; i <= n; i++){
if(mark[i] == -1){
DFS(i); //Se temos um vertice que ainda nao foi visitado apos a DFS do anterior entao
//Temos um novo grupo de amigos, inimigos dos anteriores, assim o numero de
//grupos aumenta em 1 unidade
ans++; //Incremento a resposta
}
}
cout << ans << "\n";
return 0;
}

view raw

gincana.cpp

hosted with ❤ by GitHub