Olá meus amigos nerds. Hoje vamos voltar no tempo e ajudar nossa amiga Larissa a adicionar seus amigos no Orkut (muitas recordações? kkk). Já que é isso que o problema 1368. Orkut nos pede para fazer. Mais especificamente, dados os amigos de Larissa e as restrições que eles impõe a ela (na forma de quais outros usuários ela deve ser amiga), para aceitarem seu convite, determine a ordem em que ela deve adiciona-los de modo que todos a aceitem.
Solução
Esse problema implora que usemos grafos para modela-lo (grande novidade, já que eu adoro grafos kkk). Onde os vértices representam os amigos de Larissa e existe uma aresta de a para b se b exige que Larissa seja amiga de a para aceitar seu convite. Observe que esse grafo representa as dependências para que um amigo aceite Larissa.
Em teoria de grafos, existe o conceito de ordenação topológica, que é uma ordenação dos vértices de um grafo de modo que se existe uma aresta ab então a deve vir antes de b nessa ordenação. Em outras palavras, se enxergarmos as arestas como dependências, todos os vértices que dependem de um vértice (têm uma aresta os ligando) devem vir após ele na ordenação. Oras, mas isso é exatamente o que queremos.
Assim a resposta para o problema é ordenar topologicamente o grafo. Note que pela definição de ordenação topológica o grafo deve ser acíclico, caso contrário seria impossível existir uma ordenação válida. Note ainda, que existem várias ordenações possíveis, basta permutar vértices que não dependem de ninguém em uma ordenação válida, que você obtém outra ordenação válida diferente.
Existem dois algoritmos, relativamente simples, para se obter uma ordenação topológica. Você pode encontrar uma explicação mais detalhada sobre eles aqui. Vou descrever, em linhas gerais, um deles que eu usei para resolver esse problema.
Suponha que o grafo é acíclico. A ideia é fazer uma busca em profundidade começando de algum vértice não visitado ainda. Nessa busca, as dependências de um dado vértice são visitadas depois de ele ter sido visitado. Então se eu escrever os vértices na ordem contrária que eles são visitados isso constituirá em uma ordenação válida.
Em teoria de grafos, existe o conceito de ordenação topológica, que é uma ordenação dos vértices de um grafo de modo que se existe uma aresta ab então a deve vir antes de b nessa ordenação. Em outras palavras, se enxergarmos as arestas como dependências, todos os vértices que dependem de um vértice (têm uma aresta os ligando) devem vir após ele na ordenação. Oras, mas isso é exatamente o que queremos.
Assim a resposta para o problema é ordenar topologicamente o grafo. Note que pela definição de ordenação topológica o grafo deve ser acíclico, caso contrário seria impossível existir uma ordenação válida. Note ainda, que existem várias ordenações possíveis, basta permutar vértices que não dependem de ninguém em uma ordenação válida, que você obtém outra ordenação válida diferente.
Existem dois algoritmos, relativamente simples, para se obter uma ordenação topológica. Você pode encontrar uma explicação mais detalhada sobre eles aqui. Vou descrever, em linhas gerais, um deles que eu usei para resolver esse problema.
Suponha que o grafo é acíclico. A ideia é fazer uma busca em profundidade começando de algum vértice não visitado ainda. Nessa busca, as dependências de um dado vértice são visitadas depois de ele ter sido visitado. Então se eu escrever os vértices na ordem contrária que eles são visitados isso constituirá em uma ordenação válida.
Implementação
Observe que eu primeiramente verifico se o grafo é acíclico. Isso não seria necessário se eu implementasse com um pouco mais de cuidado a ordenação topológica, mas para os fim desse problema acho que isso é suficiente.
Tem como me explica o código linha por linha ou só comentar o que tá acontecendo dentro do programa
ResponderExcluirO programa pode ser dividido em duas partes: 1 - funções para fazer a ordenação topologica (linhas 8 a 67); 2 - i/o e preenchimento do grafo (68 em diante)
Excluir