dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

pub struct UnionFind(Vec<isize>);

impl UnionFind {
    pub fn new(size: usize) -> Self {
        Self(vec![-1; size])
    }

    pub fn root(
        &mut self,
        u: usize,
    ) -> usize {
        if self.0[u] < 0 {
            return u;
        }

        let r = self.root(self.0[u] as usize);

        self.0[u] = r as isize;

        return r;
    }

    pub fn unite(
        &mut self,
        mut u: usize,
        mut v: usize,
    ) {
        u = self.root(u);

        v = self.root(v);

        if u == v {
            return;
        }

        use std::mem::swap;

        if self.0[u] > self.0[v] {
            swap(&mut u, &mut v);
        }

        self.0[u] += self.0[v];

        self.0[v] = u as isize;
    }
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test_practice2_b() {
        let cases = vec![(
            4,
            vec![
                ((1, 0, 1), 0),
                ((0, 0, 1), 2),
                ((0, 2, 3), 2),
                ((1, 0, 1), 1),
                ((1, 1, 2), 0),
                ((0, 0, 2), 2),
                ((1, 1, 3), 1),
            ],
        )];

        for (n, q) in cases {
            let mut uf = UnionFind::new(n);

            for ((t, u, v), ans) in q {
                if t == 0 {
                    uf.unite(u, v);
                } else {
                    assert_eq!(
                        if uf.root(u) == uf.root(v) { 1 } else { 0 },
                        ans
                    );
                }
            }
        }
    }
}