Olá meus amigos nerds. Hoje vamos verificar se dois códigos bancários pertencem a um mesmo banco ou não. Já que é isso que o problema 8709. Fusões nos pede para fazer. Mais especificamente, dados uma lista de bancos e uma série de fusões entre dois bancos, responder se dois bancos (identificados por seus códigos bancários) são o mesmo banco ou não.
Solução
Esse é um problema fácil. Já resolvemos alguns problemas bem parecidos aqui no blog. O único desafio aqui é fazer união de conjuntos de modo eficiente. Isso pode ser feito usando uma dijoint set forest que implementa tanto a operação de union quanto de find de forma eficiente (O(1)).
Quais os problemas semelhantes a esse?
ResponderExcluirEsse problema é relacionado a conjuntos dijuntos. Você pode navegar para outros problemas que usam conceitos similares atraves das tags, ou aqui: https://spojtricks.blogspot.com/search/label/conjunto%20disjunto
Excluir