thảo luận Leetcode mỗi ngày

use std::cmp::Ordering;

#[derive(PartialEq)]
struct Nnan(f64);

impl Eq for Nnan {}
impl PartialOrd for Nnan {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.0.partial_cmp(&other.0)
    }
}
impl Ord for Nnan {
    fn cmp(&self, other: &Self) -> Ordering {
        unsafe { self.0.partial_cmp(&other.0).unwrap_unchecked() }
    }
}

impl Solution {
    pub fn max_probability(n: i32, edges: Vec<Vec<i32>>, succ_prob: Vec<f64>, start_node: i32, end_node: i32) -> f64 {
        let succ_prob = succ_prob.as_slice();

        let n = n as usize;
        let adj_graph = &mut vec![Vec::new(); n];
        let adj_graph = adj_graph.as_mut_slice();
        for (index, edge) in edges.iter().enumerate() {
            let (a, b, prob) = (edge[0] as usize, edge[1] as usize, succ_prob[index]);
            adj_graph[a].push((b, prob));
            adj_graph[b].push((a, prob));
        }

        let (start, end) = (start_node as usize, end_node as usize);
        let max_probas = &mut vec![0.0; n];
        let max_probas = max_probas.as_mut_slice();
        max_probas[start] = 1.0;

        let visited = &mut std::collections::BinaryHeap::new();
        visited.push((Nnan(max_probas[start]), start));

        while let Some((Nnan(probab), node)) = visited.pop() {
            if node == end {
                return probab;
            }

            adj_graph[node].iter().for_each(|&(adj_node, adj_prob)| {
                let probab_to_adj = probab * adj_prob;
                if probab_to_adj > max_probas[adj_node] {
                    max_probas[adj_node] = probab_to_adj;
                    visited.push((Nnan(probab_to_adj), adj_node));
                }
            });
        }

        max_probas[end]
    }
}

class UnionFind {
    constructor () {
        this.parent = {};
    }

    find (x) {
        if (x in this.parent === false) this.parent[x] = x;
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union (x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) this.parent[rootY] = rootX;
    }

    numOfConnectedComponents () {
        const set = new Set();
        for (const k of Object.keys(this.parent)) {
            set.add(this.find(k));
        }
        return set.size;
    }
}
var removeStones = function(stones) {
    const uf = new UnionFind();
    for (const [x, y] of stones) {
        uf.union(x, y + 10001);
    }
    
    return stones.length - uf.numOfConnectedComponents();
};

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX == rootY:
            return

        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        uf = UnionFind(len(stones))
        root_x_map = dict()
        root_y_map = dict()

        for i, (x, y) in enumerate(stones):
            if x in root_x_map:
                uf.union(i, root_x_map[x])
            if y in root_y_map:
                uf.union(i, root_y_map[y])
            
            root_x_map[x] = root_y_map[y] = uf.find(i)
        
        groups = sum(1 for i in range(len(stones)) if i == uf.find(i))
        return len(stones) - groups

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        Map<Integer, List<Integer>> ROW = new HashMap<>();
        Map<Integer, List<Integer>> COL = new HashMap<>();
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        for (int[] stone : stones) {
            int i = stone[0];
            int j = stone[1];
            ROW.computeIfAbsent(i, a -> new ArrayList<Integer>());
            ROW.get(i).add(j);
            COL.computeIfAbsent(j, a -> new ArrayList<Integer>());
            COL.get(j).add(i);
        }
        int cnt = 0;// count connected components
        for (int[] stone : stones) {
            int i = stone[0];
            int j = stone[1];
            if (!visited.contains(new Pair(i, j))) {
                cnt++;
                dfs(ROW, COL, visited, i, j);
            }
        }

        return n - cnt;
    }

    public void dfs(
            Map<Integer, List<Integer>> ROW,
            Map<Integer, List<Integer>> COL,
            Set<Pair<Integer, Integer>> visited,
            int i, int j) {
        if(visited.contains(new Pair(i, j))) return;
        visited.add(new Pair(i,j));
        for(int col: ROW.get(i)){
            dfs(ROW,COL, visited, i, col);
        }   
        for(int row:COL.get(j)){
            dfs(ROW,COL,visited, row, j);
        }
    }
}

class Solution {
    public int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        for (int[] stone: stones) {
            uf.union(stone[0] + 10001, stone[1]);
        }
        return stones.length - uf.getCount();
    }

    class UnionFind {
        Map<Integer, Integer> parents;
        int count;

        public UnionFind() {
            parents = new HashMap<>();
            count = 0;
        }

        public int getCount() {
            return count;
        }

        public int find(int x) {
            if (!parents.containsKey(x)) {
                parents.put(x, x);
                count++;
            }

            if (x != parents.get(x)) {
                parents.put(x, find(parents.get(x)));
            }

            return parents.get(x);
        }

        public void union(int x, int y) {
            int xParent = find(x);
            int yParent = find(y);

            if (xParent == yParent) return;

            parents.put(xParent, yParent);
            count--;
        }
    }
}