Union Find

O que e

Union find e uma estrutura para manter grupos de elementos conectados.

Ela responde bem duas perguntas:

• esses dois itens estao no mesmo grupo?
• como uno esses grupos agora?

Quando usar

Ela aparece quando a conectividade muda ao longo do processo:

• ligar pontos
• detectar componente
• verificar se uniao cria ciclo

Erro comum

O erro clássico e tentar usar traversal completo toda vez que uma nova conexão aparece.

Se o problema faz muitas unioes e muitas consultas de conectividade, isso escala mal.

Pergunta melhor

Antes de aplicar, vale perguntar:

1. o problema fala de grupos que vao se juntando?
2. vou consultar conectividade muitas vezes?
3. o grafo esta mudando ao longo do caminho?