Union-Find

Para finalizar nosso curso, iremos aprender uma estrutura de dados mais complexa. Nesta aula aprenderemos a resolver o seguinte problema:

Inicialmente, existem conjuntos e o -ésimo conjunto contém apenas o número inteiro . São dadas algumas perguntas de dois tipos:

• Primeiro tipo: dado e , se else não pertencerem ao mesmo conjunto, funda os conjuntos desses dois em um
• Segundo tipo: dado e , verifique se e estão no mesmo conjunto

Para resolver este problema, representaremos cada número inteiro como vértices e cada conjunto como árvores. Aprenderemos mais sobre representação de grafos em outro curso. Por agora, considere que temos elementos ligados uns aos outros e uma árvore é um conjunto desses elementos 😉.

Vamos chamar de vértice representante de um elemento a raiz da sua árvore. Seja o pai do -ésimo vértice na árvore (uma raiz é o seu próprio pai). Inicialmente, (cada nó será a raiz da sua árvore).

Para responder à segunda pergunta, podemos apenas encontrar o representante dos dois inteiros e compará-los. Se forem iguais, os números estão no mesmo conjunto. Caso contrário, não estão.

Para lidar com a primeira pergunta, verificaremos primeiro se estão no mesmo conjunto, como descrito acima. Se estiverem, podemos simplesmente ignorar esta pergunta. Caso contrário, precisamos de fundir os conjuntos de e . Para tal, podemos simplesmente estabelecer uma ligação do representante de com o representante de .

#include <iostream>