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

type DSU struct {
    parent []int
    rank   []int
}

func NewDSU(n int) *DSU {
    dsu := &DSU{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        dsu.parent[i] = i
        dsu.rank[i] = 1
    }
    return dsu
}

func (dsu *DSU) Find(x int) int {
    if dsu.parent[x] != x {
        dsu.parent[x] = dsu.Find(dsu.parent[x])
    }
    return dsu.parent[x]
}

func (dsu *DSU) Union(x, y int) {
    rootX := dsu.Find(x)
    rootY := dsu.Find(y)

    if rootX != rootY {
        if dsu.rank[rootX] > dsu.rank[rootY] {
            dsu.parent[rootY] = rootX
        } else if dsu.rank[rootX] < dsu.rank[rootY] {
            dsu.parent[rootX] = rootY
        } else {
            dsu.parent[rootY] = rootX
            dsu.rank[rootX]++
        }
    }
}

func removeStones(stones [][]int) int {
    n:=len(stones)
    dsu := NewDSU(n)
    w:=make(map[int]int)
    u:=make(map[int]int)
    for i:=0;i<n;i++{
        if _, exists := w[stones[i][0]]; exists {
            dsu.Union(i,w[stones[i][0]])
        }
        if _, exists := u[stones[i][1]]; exists {
            dsu.Union(i,u[stones[i][1]])
        }
        w[stones[i][0]]=i
        u[stones[i][1]]=i
    }
    vis:=make([]int,n)
    for i:=0;i<n;i++{
        vis[i]=-1
    }
    res:=0
    for i:=0;i<n;i++{
        z:=dsu.Find(i)
        if vis[z]==-1{
            res+=1
            vis[z]=0
        }
    }
    return n-res
}

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        boolean[] visited = new boolean[n];
        int sameRolOrColStones = 0;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    list.get(i).add(j);
                    list.get(j).add(i);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(list, visited, i);
                sameRolOrColStones++;
            }
        }
        return n - sameRolOrColStones;
    }

    private void dfs(List<List<Integer>> list, boolean[] visited, int index) {
        visited[index] = true;
        for (int direction : list.get(index)) {
            if (!visited[direction]) {
                dfs(list, visited, direction);
            }
        }
    }
}

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        parent = [-1] * n
        result = 0

        def find(node):
            if parent[node] == -1:
                return node
            parent[node] = find(parent[node])
            return parent[node]
        
        def union(u, v):
            u = find(u)
            v = find(v)
            if u == v:
                return 0
            
            parent[u] = v
            return 1
        
        for i in range(n):
            for j in range(i+1, n):
                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                    result += union(i, j)
        return result

#[derive(Debug)]
pub struct UnionFind {
    parents: Vec<usize>,
    ranks: Vec<usize>,
    set_count: usize,
    set_sizes: Vec<usize>
}

impl UnionFind {
    pub fn new(size: usize) -> Self {
        let parents = (0..size).collect();

        let ranks = vec![0; size];
        let set_sizes = vec![1; size];

        Self {
            parents,
            ranks,
            set_count: size,
            set_sizes
        }
    }

    pub fn find_set(&mut self, i: usize) -> usize {
        if self.parents[i] == i {
            i
        } else {
            self.parents[i] = self.find_set(self.parents[i]);

            self.parents[i]
        }
    }

    pub fn same_set(&mut self, i: usize, j: usize) -> bool {
        self.find_set(i) == self.find_set(j)
    }

    pub fn union(&mut self, i: usize, j: usize) {
        if self.same_set(i, j) {
            return;
        }

        let mut set_i = self.find_set(i);
        let mut set_j = self.find_set(j);

        if self.ranks[set_i] > self.ranks[set_j] {
            (set_i, set_j) = (set_j, set_i);
        }

        if self.ranks[set_i] == self.ranks[set_j] {
            self.ranks[set_j] += 1;
        }

        self.set_sizes[set_j] += self.set_sizes[set_i];

        self.parents[set_i] = set_j;
        self.set_count -= 1;
    }

    pub fn set_count(&self) -> usize {
        self.set_count
    }

    pub fn set_size(&mut self, i: usize) -> usize {
        let set_i = self.find_set(i);

        self.set_sizes[set_i]
    }
}

use std::collections::*;

impl Solution {
    pub fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
        let n = stones.len();

        let coord_to_index: HashMap<(i32, i32), usize> =
            stones.iter().enumerate().map(|(i, pair)| ((pair[0], pair[1]), i)).collect();

        let (mut h_map, mut v_map) =
            (HashMap::<i32, Vec<i32>>::new(), HashMap::<i32, Vec<i32>>::new());

        for pair in &stones {
            let (x, y) = (pair[0], pair[1]);

            h_map.entry(x).
                and_modify(|list| list.push(y)).
                or_insert(vec![y]);

            v_map.entry(y).
                and_modify(|list| list.push(x)).
                or_insert(vec![x]);
        }

        let mut uf = UnionFind::new(n);

        for (&x, ys) in h_map.iter() {
            let y = ys[0];
            let i = coord_to_index[&(x, y)];

            for &y in ys.iter().skip(1) {
                let j = coord_to_index[&(x, y)];

                uf.union(i, j);
            }
        }

        for (&y, xs) in v_map.iter() {
            let x = xs[0];
            let i = coord_to_index[&(x, y)];

            for &x in xs.iter().skip(1) {
                let j = coord_to_index[&(x, y)];

                uf.union(i, j);
            }
        }

        (n - uf.set_count()) as i32
    }
}

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)

        parent = [-1] * n
        def find(x):
            if parent[x] == -1 or parent[x] == x: return x
            parent[x] = find(parent[x])
            return parent[x]
        
        def union(i , j):
            ii = find(i)
            jj = find(j)
            if ii == jj: return 0
            parent[ii] = jj
            return 1
        
        res = 0
        for i in range(n):
            for j in range(i + 1 , n):
                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: res += union(i , j)
        
        return res