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

por

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:

https://gist.github.com/sofhiasouza/fb0dfc6f95d1e275023656370ef672ee