Union-Find

py_union-find.py

MAXN = 1000010

parent = [0]*MAXN
size = [0]*MAXN

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def merge(i, j):
    i = find(i)
    j = find(j)
    if i == j:
        return
    if size[i] >= size[j]:
        parent[j] = i
        size[i] += size[j]
    else:
        parent[i] = j
        size[j] += size[i]

n, q = map(int, input().split())
for i in range(n):
    size[i] = 1
    parent[i] = i

for i in range(q):
    qtype, a, b = map(int, input().split())

    if qtype == 1:
        if find(a) == find(b):
            print("Mesmo conjunto")
        else:
            print("Conjuntos diferentes")
    else:
        merge(a, b)

union-find.cpp

// Implementando União por tamanho e Compressão de caminhos
// Complexidade: O(Q*α(N))
// α(N) -> inversa da Função de Ackermann
// Podemos assumir que α(N) <= 5

#include <iostream>
using namespace std;

const int MAXN = 1000010;
int parent[MAXN], tam[MAXN];

int find(int x)
{
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}

void merge(int i, int j)
{
    i = find(i);
    j = find(j);
    if (i == j)
        return;
    if (tam[i] >= tam[j])
    {
        parent[j] = i;
        tam[i] += tam[j];
    }
    else
    {
        parent[i] = j;
        tam[j] += tam[i];
    }
}

int main()
{
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++)
    {
        tam[i] = 1;
        parent[i] = i;
    }

    for (int i = 0; i < q; i++)
    {
        int type, a, b;
        cin >> type >> a >> b;

        if (type == 1)
        {
            if (find(a) == find(b))
                cout << "Mesmo conjunto\n";
            else
                cout << "Conjuntos diferentes\n";
        }
        else
            merge(a, b);
    }
    
    return 0;
}

union-find_main.cpp

// Ideia da Union-Find

// Algoritmo lento. Para cada pergunta, encontrar o representante do conjunto(subir através de algumas ligações) -> O(N)
// Complexidade: O(N*Q)

#include <iostream>
using namespace std;

const int MAXN = 1010; // maior quantidade de elementos
int parent[MAXN];      // parent[i] -> pai do i-ésimo valor

int find(int x) // Retorna o representante de x
{
    if (parent[x] == x) // Se x for a raiz(representante)
        return x;
    return find(parent[x]);
}

void merge(int i, int j) // Faz a fusão dos conjuntos que contém i e j
{
    i = find(i);
    j = find(j);
    if (i != j)        // Se não estiverem no mesmo conjunto
        parent[i] = j; // Cria uma nova ligação
}

int main()
{
    int n, q; // Número de conjuntos e número de perguntas
    cin >> n >> q;

    for (int i = 0; i < n; i++)
        parent[i] = i; // Cada valor é a raiz de seu próprio conjunto

    for (int i = 0; i < q; i++)
    {
        int type, a, b;
        cin >> type >> a >> b; // Descrição da pergunta

        if (type == 1)
        {
            if (find(a) == find(b))
                cout << "Mesmo conjunto\n";
            else
                cout << "Conjuntos diferentes\n";
        }
        else
            merge(a, b);
    }

    return 0;
}

/*

ENTRADA:
5 4
2 2 3
1 1 2
2 1 3
1 1 2
SAÍDA:
Conjuntos diferentes
Mesmo conjunto

*/

union-size.cpp

// Implementando União por tamanho (small-to-large)
// Complexidade: O(Q*log N)

#include <iostream>
using namespace std;

const int MAXN = 1010;
int parent[MAXN], tam[MAXN]; // tam[i] -> número de valores que tem uma ligação direta ou indireta a i

int find(int x)
{
    if (parent[x] == x)
        return x;
    return find(parent[x]);
}

void merge(int i, int j)
{
    i = find(i);
    j = find(j);
    if (i == j)
        return;
    if (tam[i] >= tam[j])
    {
        parent[j] = i;
        tam[i] += tam[j]; // Atualiza tam[i] com a nova ligação com j
    }
    else
    {
        parent[i] = j;
        tam[j] += tam[i]; // Atualiza tam[j] com a nova ligação com i
    }
}

int main()
{
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++)
    {
        tam[i] = 1; // Apenas i é diretamente ou indiretamente ligado a si mesmo
        parent[i] = i;
    }

    for (int i = 0; i < q; i++)
    {
        int type, a, b;
        cin >> type >> a >> b;

        if (type == 1)
        {
            if (find(a) == find(b))
                cout << "Mesmo conjunto\n";
            else
                cout << "Conjuntos diferentes\n";
        }
        else
            merge(a, b);
    }

    return 0;
}