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

Solução por Sofhia Souza

Podemos pensar nos funcionários como vértices, e as relações de superioridade como arestas. Com isso, teremos uma ou mais árvores (pois cada vértice tem no máximo um pai, e não existem ciclos). Como dito no problema, dois funcionários não podem estar no mesmo grupo caso um deles seja superior ao outro. Com isso, podemos perceber que a quantidade mínima de grupos necessários será o tamanho da maior sequência de funcionários que são superiores a um determinado X, ou seja, será igual à maior altura entre as árvores. Para descobrirmos isso, basta fazemos uma dfs em todas as árvores e imprimirmos a maior altura. Segue o código para melhor entendimento:


#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10; //valor maximo de n
int n;
vector < int > grafo[maxn];
int dfs(int u)
{
int r = 1;
for(int i = 0 ; i < grafo[u].size() ; i++) //chamo pros filhos de u
{
int v = grafo[u][i];
r = max(r, 1+dfs(v)); //pego a maior altura entre os meus filhos
}
return r;//retorno a maior altura da subarvore de u
}
int main()
{
cin >> n;
vector < int > aux; //vetor onde guardarei as raizes das arvores (os vertices que nao possuem pai)
for(int i = 1 ; i <= n ; i++)
{
int x;
cin >> x; //pai de i
if(x == -1) aux.push_back(i); //se nao possui pai, coloco no vetor aux
else grafo[x].push_back(i); //se possui pai, me conecto ao meu pai
}
int resp = 0;
for(int i = 0 ; i < aux.size() ; i++)
{
int u = aux[i];
resp = max(resp, dfs(u)); //salvo em resp a maior altura entre a que eu ja tinha e a que calculp agora, de u
}
cout << resp << "\n"; //imprimo a resposta
}