Union Find
Nesse artigo vamos apresentar vários conteúdos produzidos pela comunidade brasileira sobre Union Find.
Conteúdos em texto
NOIC
No site NOIC existem dois textos sobre Union Find:
Union Find: introdução do assunto.
Union Find++: mostrando algumas aplicações diferentes de assunto.
Conteúdos em vídeo
É bem comum o Union Find ser explicado junto com o algoritmo de Árvore Geradora Mínima (Kruskal). Então o começo dos vídeos abaixo podem ajudar a entender o Union Find.
GEMA ICMC
BITSET! 🎈GEMA Tricks #7🎈
Descrição do vídeo: algoritmos Union Find para Disjoint Set Union (DSU) e Kruskal para Minimum Spanning Tree (MST).
MaratonUSP
Union-find e Kruskal
Maratona UFMG
Aula 10 - DSU e Kruskal
Descrição do vídeo: na aula apresentamos, pouco a pouco, o raciocínio e otimizações necessários para se criar uma estrutura que faz operações do tipo "união de conjuntos disjuntos" e mostramos um pouco da ideia por trás da sua complexidade. Além disso prova-se a corretude e implementa-se o algoritmo de Kruskal, um algoritmo muito eficiente para encontrar árvores geradoras mínimas de um grafo.
Seletiva da IOI 2021
DSU e tricks
Aula de Tiago Domingos Souza (tdas)
Descrição: aula trata desde uma introdução e depois insere truques mais avançados, como:
Roolback: desfazendo a última operação de merge
small-to-large: como manter outras propriedades de cada conjunto de forma eficiente
min(x,n-x) trick: um truque pouco comum, mas bastante interessante
Para mais aulas da seletiva da IOI acesse esse link do site da OBI.