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

Solução por Sofhia Souza

Se notarmos bem, os alunos representam os vértices, e as relações de amizade entre os colegas representam as arestas de um grafo. Para sabermos o tamanho do maior grupo de amizade, basta descobrirmos o tamanho da maior componente conexa! Para isso, usaremos o algoritmo Flood Fill (caso não tenha estudado ainda, veja a aula NOIC sobre o assunto). Para cada componente, contamos a quantidade de vértices existentes nela e guardamos a maior, depois basta imprimi-la!

Segue o código para melhor entendimento:


#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10; //declaro maxn como o valor maximo do meu n
int n, m, vist[maxn], qtd; //vist é meu vetor de visitados, que começa zerado
vector < int > grafo[maxn];
void dfs(int u)
{
vist[u] = 1;
qtd++; //pra cada vértice que eu visito, é um vértice a mais no tamanho da minha componente
for(int i = 0 ; i < grafo[u].size() ; i++)
{
int v = grafo[u][i];
if(!vist[v]) dfs(v);
}
}
int main()
{
cin >> n >> m;
for(int i = 0 ; i < m ; i++)
{
int a, b;
cin >> a >> b;
grafo[a].push_back(b);
grafo[b].push_back(a);
}
int maior = 0; //variável onde irei guardar o tamanho da maior componente
for(int i = 1 ; i <= n ; i++)
{
qtd = 0; //qtd é a variável que irei usar para contar a quantidade de vértices existentes na componente
if(!vist[i])
{
dfs(i);
maior = max(maior, qtd); //se o tamanho dessa componente for maior do que a que eu tinha guardado antes, substituo
}
}
cout << maior << "\n";
}