Solução Informática - Nível Intermediário - Semana 31

Escrito por Enzo Dantas

Conhecimento prévio necessário

Primeiramente vamos ordenar o vetor, pois, dessa maneira, o usuário mais perto do usuário i é ou o usuário a esquerda dele ou o usuário a direita dele. Em seguida, vamos criar uma aresta direcionada do usuário i para o usuário mais próximo dele (o usuário da esquerda ou da direita), criando assim um grafo.

Perceba que, se não houver nenhuma aresta "entrando" em um certo vértice, ele nunca será chamado, a não ser pelo sistema central. Sendo assim, vamos chamar todos esses vértices e marcar todos os vértices chamados como visitados. Feito isso, perceba que sobraram apenas componentes que são um ciclo, ou seja, que não possuem nenhum vértice i com degin_i=0. Se eu tenho uma dessas componentes, não importa qual vértice eu vou chamar inicialmente, pois qualquer um vai visitar toda a componente. Sendo assim, para cada vértice que ainda não tiver sido visitado, vou chamar ele e, durante a DFS, marcar toda a componente como visitado.

É recomendado tentar implementar a solução antes de ver o código.