Union-Find (Disjoint Set) em Rust

/// Union-Find (Disjoint Set Union) com path compression e union by rank.
/// Complexidade amortizada: O(α(n)) por operação, onde α é a inversa de Ackermann.
struct UnionFind {
    /// parent[i] = pai do elemento i (raiz se parent[i] == i)
    parent: Vec<usize>,
    /// rank[i] = limite superior da altura da árvore com raiz i
    rank: Vec<usize>,
    /// tamanho[i] = número de elementos no conjunto com raiz i
    tamanho: Vec<usize>,
    /// Número de conjuntos disjuntos
    num_conjuntos: usize,
}

impl UnionFind {
    /// Cria um Union-Find com n elementos, cada um em seu próprio conjunto.
    fn novo(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),  // Cada elemento é seu próprio pai
            rank: vec![0; n],           // Rank inicial é 0
            tamanho: vec![1; n],        // Cada conjunto tem tamanho 1
            num_conjuntos: n,
        }
    }

    /// Encontra o representante (raiz) do conjunto que contém x.
    /// Usa path compression: todos os nós no caminho apontam direto para a raiz.
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            // Path compression: faz x apontar diretamente para a raiz
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    /// Une os conjuntos que contêm x e y.
    /// Usa union by rank: a árvore menor fica sob a maior.
    /// Retorna true se os conjuntos foram efetivamente unidos (estavam separados).
    fn union(&mut self, x: usize, y: usize) -> bool {
        let raiz_x = self.find(x);
        let raiz_y = self.find(y);

        // Já pertencem ao mesmo conjunto
        if raiz_x == raiz_y {
            return false;
        }

        // Union by rank: árvore menor fica sob a maior
        match self.rank[raiz_x].cmp(&self.rank[raiz_y]) {
            std::cmp::Ordering::Less => {
                self.parent[raiz_x] = raiz_y;
                self.tamanho[raiz_y] += self.tamanho[raiz_x];
            }
            std::cmp::Ordering::Greater => {
                self.parent[raiz_y] = raiz_x;
                self.tamanho[raiz_x] += self.tamanho[raiz_y];
            }
            std::cmp::Ordering::Equal => {
                self.parent[raiz_y] = raiz_x;
                self.tamanho[raiz_x] += self.tamanho[raiz_y];
                self.rank[raiz_x] += 1; // Rank aumenta somente quando iguais
            }
        }

        self.num_conjuntos -= 1;
        true
    }

    /// Verifica se x e y pertencem ao mesmo conjunto.
    fn conectados(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    /// Retorna o tamanho do conjunto que contém x.
    fn tamanho_conjunto(&mut self, x: usize) -> usize {
        let raiz = self.find(x);
        self.tamanho[raiz]
    }

    /// Retorna o número de conjuntos disjuntos.
    fn num_conjuntos(&self) -> usize {
        self.num_conjuntos
    }

    /// Exibe o estado atual do Union-Find.
    fn exibir(&mut self) {
        let n = self.parent.len();
        println!("Union-Find: {} elementos, {} conjuntos", n, self.num_conjuntos);

        // Agrupa elementos por conjunto
        let mut grupos: std::collections::HashMap<usize, Vec<usize>> =
            std::collections::HashMap::new();
        for i in 0..n {
            let raiz = self.find(i);
            grupos.entry(raiz).or_default().push(i);
        }

        for (raiz, membros) in &grupos {
            println!("  Conjunto (raiz={}): {:?} (tamanho={})", raiz, membros, membros.len());
        }
    }
}

/// Versão com find iterativo para evitar stack overflow em conjuntos muito grandes
struct UnionFindIterativo {
    parent: Vec<usize>,
    rank: Vec<usize>,
    tamanho: Vec<usize>,
    num_conjuntos: usize,
}

impl UnionFindIterativo {
    fn novo(n: usize) -> Self {
        UnionFindIterativo {
            parent: (0..n).collect(),
            rank: vec![0; n],
            tamanho: vec![1; n],
            num_conjuntos: n,
        }
    }

    /// Find iterativo com path compression em duas passagens
    fn find(&mut self, mut x: usize) -> usize {
        // Primeira passagem: encontra a raiz
        let mut raiz = x;
        while self.parent[raiz] != raiz {
            raiz = self.parent[raiz];
        }

        // Segunda passagem: comprime o caminho
        while self.parent[x] != raiz {
            let proximo = self.parent[x];
            self.parent[x] = raiz;
            x = proximo;
        }

        raiz
    }

    /// Find com "path halving" — alternativa mais simples
    /// Cada nó aponta para o avô (pula um nível)
    fn find_halving(&mut self, mut x: usize) -> usize {
        while self.parent[x] != x {
            self.parent[x] = self.parent[self.parent[x]]; // Aponta para o avô
            x = self.parent[x];
        }
        x
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let raiz_x = self.find(x);
        let raiz_y = self.find(y);

        if raiz_x == raiz_y {
            return false;
        }

        if self.rank[raiz_x] < self.rank[raiz_y] {
            self.parent[raiz_x] = raiz_y;
            self.tamanho[raiz_y] += self.tamanho[raiz_x];
        } else if self.rank[raiz_x] > self.rank[raiz_y] {
            self.parent[raiz_y] = raiz_x;
            self.tamanho[raiz_x] += self.tamanho[raiz_y];
        } else {
            self.parent[raiz_y] = raiz_x;
            self.tamanho[raiz_x] += self.tamanho[raiz_y];
            self.rank[raiz_x] += 1;
        }

        self.num_conjuntos -= 1;
        true
    }

    fn conectados(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// Representa uma aresta ponderada para Kruskal
#[derive(Debug, Clone)]
struct Aresta {
    u: usize,
    v: usize,
    peso: i64,
}

/// Algoritmo de Kruskal para encontrar a Árvore Geradora Mínima (MST).
/// Usa Union-Find para detectar ciclos eficientemente.
fn kruskal(num_vertices: usize, mut arestas: Vec<Aresta>) -> (i64, Vec<Aresta>) {
    // Ordena arestas por peso crescente
    arestas.sort_by_key(|a| a.peso);

    let mut uf = UnionFind::novo(num_vertices);
    let mut mst: Vec<Aresta> = Vec::new();
    let mut custo_total: i64 = 0;

    for aresta in &arestas {
        // Se u e v não estão no mesmo conjunto, adiciona a aresta
        if uf.union(aresta.u, aresta.v) {
            custo_total += aresta.peso;
            mst.push(aresta.clone());

            // MST tem exatamente V-1 arestas
            if mst.len() == num_vertices - 1 {
                break;
            }
        }
    }

    (custo_total, mst)
}

/// Simulação de rede de computadores
struct RedeComputadores {
    uf: UnionFind,
    nomes: Vec<String>,
    conexoes: Vec<(usize, usize, String)>, // (origem, destino, tipo)
}

impl RedeComputadores {
    fn nova(computadores: Vec<&str>) -> Self {
        let n = computadores.len();
        RedeComputadores {
            uf: UnionFind::novo(n),
            nomes: computadores.into_iter().map(String::from).collect(),
            conexoes: Vec::new(),
        }
    }

    fn indice(&self, nome: &str) -> Option<usize> {
        self.nomes.iter().position(|n| n == nome)
    }

    /// Conecta dois computadores
    fn conectar(&mut self, a: &str, b: &str, tipo_conexao: &str) {
        if let (Some(i), Some(j)) = (self.indice(a), self.indice(b)) {
            if self.uf.union(i, j) {
                self.conexoes.push((i, j, tipo_conexao.to_string()));
                println!(
                    "  Conectados: {} <-> {} via {} (redes distintas: {})",
                    a, b, tipo_conexao, self.uf.num_conjuntos()
                );
            } else {
                println!(
                    "  {} e {} já estão na mesma rede (conexão {} ignorada)",
                    a, b, tipo_conexao
                );
            }
        }
    }

    /// Verifica se dois computadores podem se comunicar
    fn podem_comunicar(&mut self, a: &str, b: &str) -> bool {
        match (self.indice(a), self.indice(b)) {
            (Some(i), Some(j)) => self.uf.conectados(i, j),
            _ => false,
        }
    }

    /// Retorna o número de redes isoladas
    fn redes_isoladas(&self) -> usize {
        self.uf.num_conjuntos()
    }

    /// Exibe estado da rede
    fn exibir(&mut self) {
        println!("╔═══════════════════════════════════════════╗");
        println!("║        Estado da Rede                     ║");
        println!("╠═══════════════════════════════════════════╣");
        println!("║ Computadores: {}                          ", self.nomes.len());
        println!("║ Conexões: {}                              ", self.conexoes.len());
        println!("║ Redes isoladas: {}                        ", self.redes_isoladas());
        println!("╠═══════════════════════════════════════════╣");
        self.uf.exibir();
        println!("╚═══════════════════════════════════════════╝");
    }
}

fn main() {
    // === Kruskal's MST ===
    println!("=== Árvore Geradora Mínima (Kruskal) ===\n");

    // Grafo: cidades conectadas com custos de fibra óptica
    let cidades = vec!["SP", "RJ", "BH", "BSB", "CWB", "POA"];
    let arestas = vec![
        Aresta { u: 0, v: 1, peso: 400 },  // SP - RJ
        Aresta { u: 0, v: 2, peso: 580 },  // SP - BH
        Aresta { u: 0, v: 4, peso: 410 },  // SP - CWB
        Aresta { u: 1, v: 2, peso: 440 },  // RJ - BH
        Aresta { u: 2, v: 3, peso: 740 },  // BH - BSB
        Aresta { u: 3, v: 1, peso: 1150 }, // BSB - RJ
        Aresta { u: 4, v: 5, peso: 710 },  // CWB - POA
        Aresta { u: 0, v: 5, peso: 1100 }, // SP - POA
        Aresta { u: 0, v: 3, peso: 1010 }, // SP - BSB
    ];

    let (custo, mst) = kruskal(cidades.len(), arestas);

    println!("Arestas da MST:");
    for aresta in &mst {
        println!(
            "  {} -- {} (custo: R$ {}k)",
            cidades[aresta.u], cidades[aresta.v], aresta.peso
        );
    }
    println!("Custo total: R$ {}k\n", custo);

    // === Rede de Computadores ===
    println!("=== Simulação de Rede de Computadores ===\n");

    let mut rede = RedeComputadores::nova(vec![
        "Servidor-A", "Servidor-B", "Servidor-C",
        "Desktop-1", "Desktop-2", "Laptop-1",
        "Laptop-2", "IoT-1",
    ]);

    println!("Conectando dispositivos:");
    rede.conectar("Servidor-A", "Servidor-B", "Ethernet 10Gbps");
    rede.conectar("Servidor-B", "Servidor-C", "Ethernet 10Gbps");
    rede.conectar("Desktop-1", "Desktop-2", "Ethernet 1Gbps");
    rede.conectar("Laptop-1", "Laptop-2", "Wi-Fi 6");

    println!("\nAntes de conectar redes:");
    println!(
        "  Servidor-A <-> Desktop-1? {}",
        rede.podem_comunicar("Servidor-A", "Desktop-1")
    );

    rede.conectar("Servidor-C", "Desktop-1", "Ethernet 1Gbps");

    println!("\nDepois de conectar redes:");
    println!(
        "  Servidor-A <-> Desktop-2? {}",
        rede.podem_comunicar("Servidor-A", "Desktop-2")
    );

    // Conexão redundante
    rede.conectar("Servidor-A", "Desktop-2", "Ethernet (redundante)");

    // Conecta rede Wi-Fi ao restante
    rede.conectar("Laptop-1", "Desktop-1", "Wi-Fi 6");

    println!();
    rede.exibir();
}

fn numero_de_ilhas(grade: &[Vec<char>]) -> usize {
    // Dica: para cada célula de terra, faça union com seus vizinhos de terra
    // O número de conjuntos de terra no final é o número de ilhas
    todo!()
}

// Teste:
// [['1','1','0','0'],
//  ['1','0','0','1'],
//  ['0','0','1','1']]
// => 3 ilhas

fn arestas_redundantes(n: usize, arestas: &[(usize, usize)]) -> usize {
    // Dica: conte quantas vezes union retorna false
    todo!()
}

struct UnionFindComHistorico {
    parent: Vec<usize>,
    rank: Vec<usize>,
    historico: Vec<(usize, usize, usize, usize)>, // (raiz_x, raiz_y, rank_x, rank_y)
    num_conjuntos: usize,
}

impl UnionFindComHistorico {
    fn novo(n: usize) -> Self { todo!() }
    fn find(&self, x: usize) -> usize { todo!() } // SEM path compression!
    fn union(&mut self, x: usize, y: usize) -> bool { todo!() }
    fn desfazer(&mut self) -> bool { todo!() } // Desfaz a última union
}