Olá meus amigos nerds, enquanto alguém não inventar um remédio mágico para garganta inflamada (minha garganta agradeceria) vamos resolver mais problemas.
O problema de hoje é o 1737. Mesa da Sra Montagny! e nele vamos ajudar a sra Montagny a decidir se é possível dispor todos os seus convidados numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.
Solução
Como não vejo a hora de me deitar para descansar vou resolver problema de forma bem rápida. O problema nos fornece as relações de amizade dos convidados, isso sugere fortemente que a utilização de grafos é uma boa ideia para o problema.
Para que seja possível dispor os convidados, não pode haver um convidado que possua amigos dos dois lados da mesa. Se pensarmos os lados da mesa como conjuntos de vértices, qual tipo de grafo tem essa propriedade? Grafos bipartidos. Então o problema nos pede para identificar se o grafo é bipartido. Caso o grafo formado pelas relações de amizade seja bipartido, a sra Montagny poderá dispor seus convidados na mesa, caso contrário não.
Identificar se um grafo é bipartido é fácil. Basta fazer uma busca em profundidade, marcando os vértices de um dos conjuntos de uma cor e os do outro conjunto com outra. Caso eu encontre um vértice que deveria ter uma cor mas ele tem outra então o grafo não é bipartido, caso contrário ele é.
P.S. prometo que semana que vem falo de um problema mais interessante, mas hoje minha garganta me pede para fazer outras coisas rsrs
Para que seja possível dispor os convidados, não pode haver um convidado que possua amigos dos dois lados da mesa. Se pensarmos os lados da mesa como conjuntos de vértices, qual tipo de grafo tem essa propriedade? Grafos bipartidos. Então o problema nos pede para identificar se o grafo é bipartido. Caso o grafo formado pelas relações de amizade seja bipartido, a sra Montagny poderá dispor seus convidados na mesa, caso contrário não.
Identificar se um grafo é bipartido é fácil. Basta fazer uma busca em profundidade, marcando os vértices de um dos conjuntos de uma cor e os do outro conjunto com outra. Caso eu encontre um vértice que deveria ter uma cor mas ele tem outra então o grafo não é bipartido, caso contrário ele é.
P.S. prometo que semana que vem falo de um problema mais interessante, mas hoje minha garganta me pede para fazer outras coisas rsrs
Nenhum comentário:
Postar um comentário