Grafo com Lista de Adjacência em Rust

/// Grafo não-direcionado usando Vec<Vec<usize>>
struct GrafoSimples {
    /// Lista de adjacência: adj[v] contém os vizinhos de v
    adj: Vec<Vec<usize>>,
    /// Número de vértices
    num_vertices: usize,
    /// Número de arestas
    num_arestas: usize,
}

impl GrafoSimples {
    /// Cria um grafo com n vértices e sem arestas
    fn novo(num_vertices: usize) -> Self {
        GrafoSimples {
            adj: vec![Vec::new(); num_vertices],
            num_vertices,
            num_arestas: 0,
        }
    }

    /// Adiciona uma aresta não-direcionada entre u e v
    fn adicionar_aresta(&mut self, u: usize, v: usize) {
        assert!(u < self.num_vertices && v < self.num_vertices);
        self.adj[u].push(v);
        self.adj[v].push(u);
        self.num_arestas += 1;
    }

    /// Retorna os vizinhos do vértice v
    fn vizinhos(&self, v: usize) -> &[usize] {
        &self.adj[v]
    }

    /// Grau do vértice (número de conexões)
    fn grau(&self, v: usize) -> usize {
        self.adj[v].len()
    }

    /// Exibe o grafo
    fn exibir(&self) {
        println!("Grafo: {} vértices, {} arestas", self.num_vertices, self.num_arestas);
        for (v, vizinhos) in self.adj.iter().enumerate() {
            println!("  {} -> {:?}", v, vizinhos);
        }
    }
}

use std::collections::VecDeque;

/// Realiza BFS a partir de um vértice de origem.
/// Retorna o vetor de distâncias (-1 se não alcançável).
fn bfs(grafo: &GrafoSimples, origem: usize) -> Vec<i32> {
    let n = grafo.num_vertices;
    let mut distancia = vec![-1i32; n];
    let mut fila = VecDeque::new();

    distancia[origem] = 0;
    fila.push_back(origem);

    while let Some(atual) = fila.pop_front() {
        for &vizinho in grafo.vizinhos(atual) {
            if distancia[vizinho] == -1 {
                distancia[vizinho] = distancia[atual] + 1;
                fila.push_back(vizinho);
            }
        }
    }

    distancia
}

/// BFS que também retorna o caminho (predecessores)
fn bfs_com_caminho(grafo: &GrafoSimples, origem: usize) -> (Vec<i32>, Vec<Option<usize>>) {
    let n = grafo.num_vertices;
    let mut distancia = vec![-1i32; n];
    let mut predecessor: Vec<Option<usize>> = vec![None; n];
    let mut fila = VecDeque::new();

    distancia[origem] = 0;
    fila.push_back(origem);

    while let Some(atual) = fila.pop_front() {
        for &vizinho in grafo.vizinhos(atual) {
            if distancia[vizinho] == -1 {
                distancia[vizinho] = distancia[atual] + 1;
                predecessor[vizinho] = Some(atual);
                fila.push_back(vizinho);
            }
        }
    }

    (distancia, predecessor)
}

/// Reconstrói o caminho de origem a destino usando predecessores
fn reconstruir_caminho(predecessor: &[Option<usize>], destino: usize) -> Vec<usize> {
    let mut caminho = Vec::new();
    let mut atual = Some(destino);

    while let Some(v) = atual {
        caminho.push(v);
        atual = predecessor[v];
    }

    caminho.reverse();
    caminho
}

/// DFS iterativa usando pilha explícita
fn dfs_iterativa(grafo: &GrafoSimples, origem: usize) -> Vec<usize> {
    let n = grafo.num_vertices;
    let mut visitado = vec![false; n];
    let mut ordem = Vec::new();
    let mut pilha = vec![origem];

    while let Some(atual) = pilha.pop() {
        if visitado[atual] {
            continue;
        }
        visitado[atual] = true;
        ordem.push(atual);

        // Adiciona vizinhos na pilha (em ordem reversa para manter ordem natural)
        for &vizinho in grafo.vizinhos(atual).iter().rev() {
            if !visitado[vizinho] {
                pilha.push(vizinho);
            }
        }
    }

    ordem
}

/// DFS recursiva
fn dfs_recursiva(grafo: &GrafoSimples, origem: usize) -> Vec<usize> {
    let n = grafo.num_vertices;
    let mut visitado = vec![false; n];
    let mut ordem = Vec::new();

    fn dfs_helper(
        grafo: &GrafoSimples,
        v: usize,
        visitado: &mut Vec<bool>,
        ordem: &mut Vec<usize>,
    ) {
        visitado[v] = true;
        ordem.push(v);

        for &vizinho in grafo.vizinhos(v) {
            if !visitado[vizinho] {
                dfs_helper(grafo, vizinho, visitado, ordem);
            }
        }
    }

    dfs_helper(grafo, origem, &mut visitado, &mut ordem);
    ordem
}

use std::collections::HashMap;

/// Grafo genérico usando HashMap para rótulos flexíveis
struct Grafo<T: Eq + std::hash::Hash + Clone> {
    /// Mapeia cada vértice para sua lista de vizinhos com pesos
    adj: HashMap<T, Vec<(T, f64)>>,
    /// Se o grafo é direcionado
    direcionado: bool,
}

impl<T: Eq + std::hash::Hash + Clone + std::fmt::Debug> Grafo<T> {
    fn novo(direcionado: bool) -> Self {
        Grafo {
            adj: HashMap::new(),
            direcionado,
        }
    }

    /// Adiciona um vértice ao grafo
    fn adicionar_vertice(&mut self, v: T) {
        self.adj.entry(v).or_insert_with(Vec::new);
    }

    /// Adiciona uma aresta com peso
    fn adicionar_aresta(&mut self, de: T, para: T, peso: f64) {
        self.adj.entry(de.clone()).or_default().push((para.clone(), peso));
        if !self.direcionado {
            self.adj.entry(para).or_default().push((de, peso));
        } else {
            // Garante que o vértice de destino exista
            self.adj.entry(para).or_default();
        }
    }

    /// Retorna os vizinhos de um vértice
    fn vizinhos(&self, v: &T) -> Option<&Vec<(T, f64)>> {
        self.adj.get(v)
    }

    /// Número de vértices
    fn num_vertices(&self) -> usize {
        self.adj.len()
    }

    /// Exibe o grafo
    fn exibir(&self) {
        let tipo = if self.direcionado { "Direcionado" } else { "Não-direcionado" };
        println!("Grafo {} ({} vértices):", tipo, self.num_vertices());
        for (v, vizinhos) in &self.adj {
            let lista: Vec<String> = vizinhos
                .iter()
                .map(|(u, p)| format!("{:?}({})", u, p))
                .collect();
            println!("  {:?} -> [{}]", v, lista.join(", "));
        }
    }
}

use std::collections::{HashMap, HashSet, VecDeque};

/// Rede social simples usando grafo não-direcionado
struct RedeSocial {
    /// Amizades: mapeia nome -> conjunto de amigos
    amizades: HashMap<String, HashSet<String>>,
}

impl RedeSocial {
    fn nova() -> Self {
        RedeSocial {
            amizades: HashMap::new(),
        }
    }

    /// Adiciona um usuário à rede
    fn adicionar_usuario(&mut self, nome: &str) {
        self.amizades.entry(nome.to_string()).or_default();
    }

    /// Cria amizade bidirecional entre dois usuários
    fn adicionar_amizade(&mut self, a: &str, b: &str) {
        self.amizades.entry(a.to_string()).or_default().insert(b.to_string());
        self.amizades.entry(b.to_string()).or_default().insert(a.to_string());
    }

    /// Retorna amigos diretos de um usuário
    fn amigos(&self, nome: &str) -> Option<&HashSet<String>> {
        self.amizades.get(nome)
    }

    /// Encontra amigos em comum entre dois usuários
    fn amigos_em_comum(&self, a: &str, b: &str) -> HashSet<String> {
        match (self.amizades.get(a), self.amizades.get(b)) {
            (Some(amigos_a), Some(amigos_b)) => {
                amigos_a.intersection(amigos_b).cloned().collect()
            }
            _ => HashSet::new(),
        }
    }

    /// Sugere amigos: amigos de amigos que ainda não são amigos diretos
    fn sugerir_amigos(&self, nome: &str) -> Vec<(String, usize)> {
        let meus_amigos = match self.amizades.get(nome) {
            Some(a) => a,
            None => return vec![],
        };

        // Conta quantas conexões em comum cada potencial amigo tem
        let mut sugestoes: HashMap<String, usize> = HashMap::new();

        for amigo in meus_amigos {
            if let Some(amigos_do_amigo) = self.amizades.get(amigo) {
                for candidato in amigos_do_amigo {
                    // Não sugerir a si mesmo nem amigos existentes
                    if candidato != nome && !meus_amigos.contains(candidato) {
                        *sugestoes.entry(candidato.clone()).or_default() += 1;
                    }
                }
            }
        }

        // Ordena por número de conexões em comum (decrescente)
        let mut resultado: Vec<(String, usize)> = sugestoes.into_iter().collect();
        resultado.sort_by(|a, b| b.1.cmp(&a.1));
        resultado
    }

    /// Grau de separação entre dois usuários (BFS)
    fn grau_separacao(&self, de: &str, para: &str) -> Option<usize> {
        if !self.amizades.contains_key(de) || !self.amizades.contains_key(para) {
            return None;
        }
        if de == para {
            return Some(0);
        }

        let mut visitado: HashSet<String> = HashSet::new();
        let mut fila: VecDeque<(String, usize)> = VecDeque::new();

        visitado.insert(de.to_string());
        fila.push_back((de.to_string(), 0));

        while let Some((atual, dist)) = fila.pop_front() {
            if let Some(amigos) = self.amizades.get(&atual) {
                for amigo in amigos {
                    if amigo == para {
                        return Some(dist + 1);
                    }
                    if visitado.insert(amigo.clone()) {
                        fila.push_back((amigo.clone(), dist + 1));
                    }
                }
            }
        }

        None // Não conectados
    }

    /// Exibe a rede social
    fn exibir(&self) {
        println!("╔══════════════════════════════╗");
        println!("║      Rede Social             ║");
        println!("╠══════════════════════════════╣");
        for (usuario, amigos) in &self.amizades {
            let lista: Vec<&str> = amigos.iter().map(|s| s.as_str()).collect();
            println!("║ {} ({} amigos): {:?}", usuario, amigos.len(), lista);
        }
        println!("╚══════════════════════════════╝");
    }
}

fn main() {
    // === Rede Social ===
    let mut rede = RedeSocial::nova();

    // Adicionando usuários e amizades
    for nome in &["Alice", "Bruno", "Carol", "Daniel", "Eva", "Felipe", "Gabi"] {
        rede.adicionar_usuario(nome);
    }

    rede.adicionar_amizade("Alice", "Bruno");
    rede.adicionar_amizade("Alice", "Carol");
    rede.adicionar_amizade("Bruno", "Carol");
    rede.adicionar_amizade("Bruno", "Daniel");
    rede.adicionar_amizade("Carol", "Eva");
    rede.adicionar_amizade("Daniel", "Eva");
    rede.adicionar_amizade("Daniel", "Felipe");
    rede.adicionar_amizade("Eva", "Gabi");

    rede.exibir();

    // Amigos em comum
    let comuns = rede.amigos_em_comum("Alice", "Daniel");
    println!("\nAmigos em comum (Alice, Daniel): {:?}", comuns);

    // Sugestões de amizade
    let sugestoes = rede.sugerir_amigos("Alice");
    println!("\nSugestões para Alice:");
    for (nome, conexoes) in &sugestoes {
        println!("  {} ({} amigos em comum)", nome, conexoes);
    }

    // Grau de separação
    let pares = vec![("Alice", "Gabi"), ("Alice", "Bruno"), ("Alice", "Felipe")];
    println!("\nGraus de separação:");
    for (a, b) in pares {
        match rede.grau_separacao(a, b) {
            Some(grau) => println!("  {} <-> {}: {} grau(s)", a, b, grau),
            None => println!("  {} <-> {}: não conectados", a, b),
        }
    }
}

fn tem_ciclo(grafo: &GrafoSimples) -> bool {
    // Dica: na DFS, se encontrar um vizinho já visitado que
    // não seja o pai, há um ciclo
    todo!()
}

fn componentes_conectados(grafo: &GrafoSimples) -> Vec<Vec<usize>> {
    // Dica: execute BFS/DFS de cada vértice não visitado
    // Cada execução descobre um novo componente
    todo!()
}

fn menor_caminho(grafo: &GrafoSimples, origem: usize, destino: usize) -> Option<Vec<usize>> {
    // Dica: use BFS com rastreamento de predecessores
    // e reconstroi o caminho ao final
    todo!()
}