UnionFindBase

competitive::data_structure::union_find

Struct UnionFindBase 

Source 
pub struct UnionFindBase<U, F, M, P, H>
where
    U: UnionStrategy,
    F: FindStrategy,
    M: UfMergeSpec,
    P: Monoid,
    H: UndoStrategy<UfCell<U, M, P>>,
{
    cells: Vec<UfCell<U, M, P>>,
    merger: M,
    history: H::History,
    _marker: PhantomData<fn() -> F>,
}

Fields§

§cells: Vec<UfCell<U, M, P>>§merger: M§history: H::History§_marker: PhantomData<fn() -> F>

Implementations§

Source§

impl<U, F, P, H> UnionFindBase<U, F, (), P, H>
where U: UnionStrategy, F: FindStrategy, P: Monoid, H: UndoStrategy<UfCell<U, (), P>>,

Source

pub fn new(n: usize) -> Self

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_1_a.rs (line 10)
6pub fn dsl_1_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            uf.unite(x, y);
15        } else {
16            writeln!(writer, "{}", (uf.same(x, y) as usize)).ok();
17        }
18    }
19}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 10)
6pub fn unionfind(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, u, v);
13        if ty == 0 {
14            uf.unite(u, v);
15        } else {
16            writeln!(writer, "{}", uf.same(u, v) as usize).ok();
17        }
18    }
19}
crates/competitive/src/graph/minimum_spanning_tree.rs (line 10)
4    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
5    where
6        T: Ord,
7    {
8        let mut idx: Vec<_> = (0..self.edges_size()).collect();
9        idx.sort_by_key(weight);
10        let mut uf = UnionFind::new(self.vertices_size());
11        let mut res = vec![false; self.edges_size()];
12        for eid in idx.into_iter() {
13            let (u, v) = self[eid];
14            res[eid] = uf.unite(u, v);
15        }
16        res
17    }
crates/aizu_online_judge/src/dsl/dsl_1_b.rs (line 10)
6pub fn dsl_1_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            scan!(scanner, w: i64);
15            uf.unite_with(x, y, w);
16        } else if let Some(w) = uf.difference(x, y) {
17            writeln!(writer, "{}", w).ok();
18        } else {
19            writeln!(writer, "?").ok();
20        }
21    }
22}
Source

pub fn push(&mut self)

Source§

impl<U, F, T, Merge, P, H> UnionFindBase<U, F, FnMerger<T, Merge>, P, H>
where U: UnionStrategy, F: FindStrategy, Merge: FnMut(&mut T, &mut T), P: Monoid, H: UndoStrategy<UfCell<U, FnMerger<T, Merge>, P>>,

Source

pub fn new_with_merger( n: usize, init: impl FnMut(usize) -> T, merge: Merge, ) -> Self

Examples found in repository?
crates/competitive/src/algorithm/solve_01_on_tree.rs (lines 55-58)
42pub fn solve_01_on_tree(
43    n: usize,
44    c01: impl Fn(usize) -> (usize, usize),
45    root: usize,
46    parent: impl Fn(usize) -> usize,
47) -> (usize, Vec<usize>) {
48    pub type UF<T, M> =
49        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
50    let mut cost = 0usize;
51    let c01 = |u| {
52        let c = c01(u);
53        Count01::new(c.0, c.1)
54    };
55    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
56        cost += x.cnt1 * y.cnt0;
57        *x += *y;
58    });
59    let mut label = vec![0; n];
60    let mut heap = BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u, 0)));
61    let mut next: Vec<_> = (0..n).collect();
62    let mut ord = Vec::with_capacity(n);
63    while let Some((_c, u, l)) = heap.pop() {
64        if label[u] != l {
65            continue;
66        }
67        let p = uf.find_root(parent(u));
68        uf.unite(u, p);
69        if !uf.same(p, root) {
70            label[p] += 1;
71            heap.push((*uf.merge_data(p), p, label[p]));
72        }
73        next.swap(u, p);
74    }
75    let mut u = next[root];
76    ord.push(u);
77    while u != root {
78        u = next[u];
79        ord.push(u);
80    }
81    ord.reverse();
82    (cost, ord)
83}
More examples
Hide additional examples
crates/competitive/src/graph/minimum_spanning_arborescence.rs (lines 31-35)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source§

impl<F, M, P, H> UnionFindBase<UnionBySize, F, M, P, H>
where F: FindStrategy, M: UfMergeSpec, P: Monoid, H: UndoStrategy<UfCell<UnionBySize, M, P>>,

Source

pub fn size(&mut self, x: usize) -> <UnionBySize as UnionStrategy>::Info

Source§

impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
where U: UnionStrategy, F: FindStrategy, M: UfMergeSpec, P: Monoid, H: UndoStrategy<UfCell<U, M, P>>,

Source

fn root_info(&mut self, x: usize) -> Option<U::Info>

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 312)
310    pub fn size(&mut self, x: usize) -> <UnionBySize as UnionStrategy>::Info {
311        let root = self.find_root(x);
312        self.root_info(root).unwrap()
313    }
314}
315
316impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
317where
318    U: UnionStrategy,
319    F: FindStrategy,
320    M: UfMergeSpec,
321    P: Monoid,
322    H: UndoStrategy<UfCell<U, M, P>>,
323{
324    fn root_info(&mut self, x: usize) -> Option<U::Info> {
325        match &self.cells[x] {
326            UfCell::Root((info, _)) => Some(info.clone()),
327            UfCell::Child(_) => None,
328        }
329    }
330
331    fn root_info_mut(&mut self, x: usize) -> Option<&mut U::Info> {
332        match &mut self.cells[x] {
333            UfCell::Root((info, _)) => Some(info),
334            UfCell::Child(_) => None,
335        }
336    }
337
338    pub fn same(&mut self, x: usize, y: usize) -> bool {
339        self.find_root(x) == self.find_root(y)
340    }
341
342    pub fn merge_data(&mut self, x: usize) -> &M::Data {
343        let root = self.find_root(x);
344        match &self.cells[root] {
345            UfCell::Root((_, data)) => data,
346            UfCell::Child(_) => unreachable!(),
347        }
348    }
349
350    pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data {
351        let root = self.find_root(x);
352        match &mut self.cells[root] {
353            UfCell::Root((_, data)) => data,
354            UfCell::Child(_) => unreachable!(),
355        }
356    }
357
358    pub fn roots(&self) -> impl Iterator<Item = usize> + '_ {
359        (0..self.cells.len()).filter(|&x| matches!(self.cells[x], UfCell::Root(_)))
360    }
361
362    pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>> {
363        let mut groups_map = HashMap::new();
364        for x in 0..self.cells.len() {
365            let r = self.find_root(x);
366            groups_map.entry(r).or_insert_with(Vec::new).push(x);
367        }
368        groups_map
369    }
370
371    pub fn find(&mut self, x: usize) -> (usize, P::T) {
372        let (parent_parent, parent_potential) = match &self.cells[x] {
373            UfCell::Child((parent, _)) => self.find(*parent),
374            UfCell::Root(_) => return (x, P::unit()),
375        };
376        let (parent, potential) = self.cells[x].child_mut().unwrap();
377        let potential = if F::CHENGE_ROOT {
378            *parent = parent_parent;
379            *potential = P::operate(&parent_potential, potential);
380            potential.clone()
381        } else {
382            P::operate(&parent_potential, potential)
383        };
384        (parent_parent, potential)
385    }
386
387    pub fn find_root(&mut self, x: usize) -> usize {
388        let (parent, parent_parent) = match &self.cells[x] {
389            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
390            UfCell::Root(_) => return x,
391        };
392        if F::CHENGE_ROOT {
393            let (cx, cp) = {
394                let ptr = self.cells.as_mut_ptr();
395                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
396            };
397            let (parent, potential) = cx.child_mut().unwrap();
398            *parent = parent_parent;
399            if let UfCell::Child((_, ppot)) = &cp {
400                *potential = P::operate(ppot, potential);
401            }
402        }
403        parent_parent
404    }
405
406    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
407        let (rx, potx) = self.find(x);
408        let ry = self.find_root(y);
409        if rx == ry || y != ry {
410            return false;
411        }
412        H::unite(&mut self.history, rx, ry, &self.cells);
413        {
414            let ptr = self.cells.as_mut_ptr();
415            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
416            self.merger
417                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
418        }
419        *self.root_info_mut(rx).unwrap() =
420            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
421        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
422        true
423    }
424}
425
426impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
427where
428    U: UnionStrategy,
429    F: FindStrategy,
430    M: UfMergeSpec,
431    P: Group,
432    H: UndoStrategy<UfCell<U, M, P>>,
433{
434    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
435        let (rx, potx) = self.find(x);
436        let (ry, poty) = self.find(y);
437        if rx == ry {
438            Some(P::operate(&P::inverse(&potx), &poty))
439        } else {
440            None
441        }
442    }
443
444    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
445        let (mut rx, potx) = self.find(x);
446        let (mut ry, poty) = self.find(y);
447        if rx == ry {
448            return false;
449        }
450        let mut xinfo = self.root_info(rx).unwrap();
451        let mut yinfo = self.root_info(ry).unwrap();
452        let inverse = !U::check_directoin(&xinfo, &yinfo);
453        let potential = if inverse {
454            P::rinv_operate(&poty, &P::operate(&potx, &potential))
455        } else {
456            P::operate(&potx, &P::rinv_operate(&potential, &poty))
457        };
458        if inverse {
459            swap(&mut rx, &mut ry);
460            swap(&mut xinfo, &mut yinfo);
461        }
462        H::unite(&mut self.history, rx, ry, &self.cells);
463        {
464            let ptr = self.cells.as_mut_ptr();
465            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
466            self.merger
467                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
468        }
469        *self.root_info_mut(rx).unwrap() = U::unite(&xinfo, &yinfo);
470        self.cells[ry] = UfCell::Child((rx, potential));
471        true
472    }
Source

fn root_info_mut(&mut self, x: usize) -> Option<&mut U::Info>

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 419)
406    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
407        let (rx, potx) = self.find(x);
408        let ry = self.find_root(y);
409        if rx == ry || y != ry {
410            return false;
411        }
412        H::unite(&mut self.history, rx, ry, &self.cells);
413        {
414            let ptr = self.cells.as_mut_ptr();
415            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
416            self.merger
417                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
418        }
419        *self.root_info_mut(rx).unwrap() =
420            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
421        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
422        true
423    }
424}
425
426impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
427where
428    U: UnionStrategy,
429    F: FindStrategy,
430    M: UfMergeSpec,
431    P: Group,
432    H: UndoStrategy<UfCell<U, M, P>>,
433{
434    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
435        let (rx, potx) = self.find(x);
436        let (ry, poty) = self.find(y);
437        if rx == ry {
438            Some(P::operate(&P::inverse(&potx), &poty))
439        } else {
440            None
441        }
442    }
443
444    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
445        let (mut rx, potx) = self.find(x);
446        let (mut ry, poty) = self.find(y);
447        if rx == ry {
448            return false;
449        }
450        let mut xinfo = self.root_info(rx).unwrap();
451        let mut yinfo = self.root_info(ry).unwrap();
452        let inverse = !U::check_directoin(&xinfo, &yinfo);
453        let potential = if inverse {
454            P::rinv_operate(&poty, &P::operate(&potx, &potential))
455        } else {
456            P::operate(&potx, &P::rinv_operate(&potential, &poty))
457        };
458        if inverse {
459            swap(&mut rx, &mut ry);
460            swap(&mut xinfo, &mut yinfo);
461        }
462        H::unite(&mut self.history, rx, ry, &self.cells);
463        {
464            let ptr = self.cells.as_mut_ptr();
465            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
466            self.merger
467                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
468        }
469        *self.root_info_mut(rx).unwrap() = U::unite(&xinfo, &yinfo);
470        self.cells[ry] = UfCell::Child((rx, potential));
471        true
472    }
Source

pub fn same(&mut self, x: usize, y: usize) -> bool

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_1_a.rs (line 16)
6pub fn dsl_1_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            uf.unite(x, y);
15        } else {
16            writeln!(writer, "{}", (uf.same(x, y) as usize)).ok();
17        }
18    }
19}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 16)
6pub fn unionfind(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, u, v);
13        if ty == 0 {
14            uf.unite(u, v);
15        } else {
16            writeln!(writer, "{}", uf.same(u, v) as usize).ok();
17        }
18    }
19}
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 69)
42pub fn solve_01_on_tree(
43    n: usize,
44    c01: impl Fn(usize) -> (usize, usize),
45    root: usize,
46    parent: impl Fn(usize) -> usize,
47) -> (usize, Vec<usize>) {
48    pub type UF<T, M> =
49        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
50    let mut cost = 0usize;
51    let c01 = |u| {
52        let c = c01(u);
53        Count01::new(c.0, c.1)
54    };
55    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
56        cost += x.cnt1 * y.cnt0;
57        *x += *y;
58    });
59    let mut label = vec![0; n];
60    let mut heap = BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u, 0)));
61    let mut next: Vec<_> = (0..n).collect();
62    let mut ord = Vec::with_capacity(n);
63    while let Some((_c, u, l)) = heap.pop() {
64        if label[u] != l {
65            continue;
66        }
67        let p = uf.find_root(parent(u));
68        uf.unite(u, p);
69        if !uf.same(p, root) {
70            label[p] += 1;
71            heap.push((*uf.merge_data(p), p, label[p]));
72        }
73        next.swap(u, p);
74    }
75    let mut u = next[root];
76    ord.push(u);
77    while u != root {
78        u = next[u];
79        ord.push(u);
80    }
81    ord.reverse();
82    (cost, ord)
83}
Source

pub fn merge_data(&mut self, x: usize) -> &M::Data

Examples found in repository?
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 71)
42pub fn solve_01_on_tree(
43    n: usize,
44    c01: impl Fn(usize) -> (usize, usize),
45    root: usize,
46    parent: impl Fn(usize) -> usize,
47) -> (usize, Vec<usize>) {
48    pub type UF<T, M> =
49        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
50    let mut cost = 0usize;
51    let c01 = |u| {
52        let c = c01(u);
53        Count01::new(c.0, c.1)
54    };
55    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
56        cost += x.cnt1 * y.cnt0;
57        *x += *y;
58    });
59    let mut label = vec![0; n];
60    let mut heap = BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u, 0)));
61    let mut next: Vec<_> = (0..n).collect();
62    let mut ord = Vec::with_capacity(n);
63    while let Some((_c, u, l)) = heap.pop() {
64        if label[u] != l {
65            continue;
66        }
67        let p = uf.find_root(parent(u));
68        uf.unite(u, p);
69        if !uf.same(p, root) {
70            label[p] += 1;
71            heap.push((*uf.merge_data(p), p, label[p]));
72        }
73        next.swap(u, p);
74    }
75    let mut u = next[root];
76    ord.push(u);
77    while u != root {
78        u = next[u];
79        ord.push(u);
80    }
81    ord.reverse();
82    (cost, ord)
83}
Source

pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 39)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

pub fn roots(&self) -> impl Iterator<Item = usize> + '_

Source

pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>>

Source

pub fn find(&mut self, x: usize) -> (usize, P::T)

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 373)
371    pub fn find(&mut self, x: usize) -> (usize, P::T) {
372        let (parent_parent, parent_potential) = match &self.cells[x] {
373            UfCell::Child((parent, _)) => self.find(*parent),
374            UfCell::Root(_) => return (x, P::unit()),
375        };
376        let (parent, potential) = self.cells[x].child_mut().unwrap();
377        let potential = if F::CHENGE_ROOT {
378            *parent = parent_parent;
379            *potential = P::operate(&parent_potential, potential);
380            potential.clone()
381        } else {
382            P::operate(&parent_potential, potential)
383        };
384        (parent_parent, potential)
385    }
386
387    pub fn find_root(&mut self, x: usize) -> usize {
388        let (parent, parent_parent) = match &self.cells[x] {
389            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
390            UfCell::Root(_) => return x,
391        };
392        if F::CHENGE_ROOT {
393            let (cx, cp) = {
394                let ptr = self.cells.as_mut_ptr();
395                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
396            };
397            let (parent, potential) = cx.child_mut().unwrap();
398            *parent = parent_parent;
399            if let UfCell::Child((_, ppot)) = &cp {
400                *potential = P::operate(ppot, potential);
401            }
402        }
403        parent_parent
404    }
405
406    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
407        let (rx, potx) = self.find(x);
408        let ry = self.find_root(y);
409        if rx == ry || y != ry {
410            return false;
411        }
412        H::unite(&mut self.history, rx, ry, &self.cells);
413        {
414            let ptr = self.cells.as_mut_ptr();
415            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
416            self.merger
417                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
418        }
419        *self.root_info_mut(rx).unwrap() =
420            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
421        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
422        true
423    }
424}
425
426impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
427where
428    U: UnionStrategy,
429    F: FindStrategy,
430    M: UfMergeSpec,
431    P: Group,
432    H: UndoStrategy<UfCell<U, M, P>>,
433{
434    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
435        let (rx, potx) = self.find(x);
436        let (ry, poty) = self.find(y);
437        if rx == ry {
438            Some(P::operate(&P::inverse(&potx), &poty))
439        } else {
440            None
441        }
442    }
443
444    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
445        let (mut rx, potx) = self.find(x);
446        let (mut ry, poty) = self.find(y);
447        if rx == ry {
448            return false;
449        }
450        let mut xinfo = self.root_info(rx).unwrap();
451        let mut yinfo = self.root_info(ry).unwrap();
452        let inverse = !U::check_directoin(&xinfo, &yinfo);
453        let potential = if inverse {
454            P::rinv_operate(&poty, &P::operate(&potx, &potential))
455        } else {
456            P::operate(&potx, &P::rinv_operate(&potential, &poty))
457        };
458        if inverse {
459            swap(&mut rx, &mut ry);
460            swap(&mut xinfo, &mut yinfo);
461        }
462        H::unite(&mut self.history, rx, ry, &self.cells);
463        {
464            let ptr = self.cells.as_mut_ptr();
465            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
466            self.merger
467                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
468        }
469        *self.root_info_mut(rx).unwrap() = U::unite(&xinfo, &yinfo);
470        self.cells[ry] = UfCell::Child((rx, potential));
471        true
472    }
Source

pub fn find_root(&mut self, x: usize) -> usize

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 311)
310    pub fn size(&mut self, x: usize) -> <UnionBySize as UnionStrategy>::Info {
311        let root = self.find_root(x);
312        self.root_info(root).unwrap()
313    }
314}
315
316impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
317where
318    U: UnionStrategy,
319    F: FindStrategy,
320    M: UfMergeSpec,
321    P: Monoid,
322    H: UndoStrategy<UfCell<U, M, P>>,
323{
324    fn root_info(&mut self, x: usize) -> Option<U::Info> {
325        match &self.cells[x] {
326            UfCell::Root((info, _)) => Some(info.clone()),
327            UfCell::Child(_) => None,
328        }
329    }
330
331    fn root_info_mut(&mut self, x: usize) -> Option<&mut U::Info> {
332        match &mut self.cells[x] {
333            UfCell::Root((info, _)) => Some(info),
334            UfCell::Child(_) => None,
335        }
336    }
337
338    pub fn same(&mut self, x: usize, y: usize) -> bool {
339        self.find_root(x) == self.find_root(y)
340    }
341
342    pub fn merge_data(&mut self, x: usize) -> &M::Data {
343        let root = self.find_root(x);
344        match &self.cells[root] {
345            UfCell::Root((_, data)) => data,
346            UfCell::Child(_) => unreachable!(),
347        }
348    }
349
350    pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data {
351        let root = self.find_root(x);
352        match &mut self.cells[root] {
353            UfCell::Root((_, data)) => data,
354            UfCell::Child(_) => unreachable!(),
355        }
356    }
357
358    pub fn roots(&self) -> impl Iterator<Item = usize> + '_ {
359        (0..self.cells.len()).filter(|&x| matches!(self.cells[x], UfCell::Root(_)))
360    }
361
362    pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>> {
363        let mut groups_map = HashMap::new();
364        for x in 0..self.cells.len() {
365            let r = self.find_root(x);
366            groups_map.entry(r).or_insert_with(Vec::new).push(x);
367        }
368        groups_map
369    }
370
371    pub fn find(&mut self, x: usize) -> (usize, P::T) {
372        let (parent_parent, parent_potential) = match &self.cells[x] {
373            UfCell::Child((parent, _)) => self.find(*parent),
374            UfCell::Root(_) => return (x, P::unit()),
375        };
376        let (parent, potential) = self.cells[x].child_mut().unwrap();
377        let potential = if F::CHENGE_ROOT {
378            *parent = parent_parent;
379            *potential = P::operate(&parent_potential, potential);
380            potential.clone()
381        } else {
382            P::operate(&parent_potential, potential)
383        };
384        (parent_parent, potential)
385    }
386
387    pub fn find_root(&mut self, x: usize) -> usize {
388        let (parent, parent_parent) = match &self.cells[x] {
389            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
390            UfCell::Root(_) => return x,
391        };
392        if F::CHENGE_ROOT {
393            let (cx, cp) = {
394                let ptr = self.cells.as_mut_ptr();
395                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
396            };
397            let (parent, potential) = cx.child_mut().unwrap();
398            *parent = parent_parent;
399            if let UfCell::Child((_, ppot)) = &cp {
400                *potential = P::operate(ppot, potential);
401            }
402        }
403        parent_parent
404    }
405
406    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
407        let (rx, potx) = self.find(x);
408        let ry = self.find_root(y);
409        if rx == ry || y != ry {
410            return false;
411        }
412        H::unite(&mut self.history, rx, ry, &self.cells);
413        {
414            let ptr = self.cells.as_mut_ptr();
415            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
416            self.merger
417                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
418        }
419        *self.root_info_mut(rx).unwrap() =
420            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
421        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
422        true
423    }
More examples
Hide additional examples
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 67)
42pub fn solve_01_on_tree(
43    n: usize,
44    c01: impl Fn(usize) -> (usize, usize),
45    root: usize,
46    parent: impl Fn(usize) -> usize,
47) -> (usize, Vec<usize>) {
48    pub type UF<T, M> =
49        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
50    let mut cost = 0usize;
51    let c01 = |u| {
52        let c = c01(u);
53        Count01::new(c.0, c.1)
54    };
55    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
56        cost += x.cnt1 * y.cnt0;
57        *x += *y;
58    });
59    let mut label = vec![0; n];
60    let mut heap = BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u, 0)));
61    let mut next: Vec<_> = (0..n).collect();
62    let mut ord = Vec::with_capacity(n);
63    while let Some((_c, u, l)) = heap.pop() {
64        if label[u] != l {
65            continue;
66        }
67        let p = uf.find_root(parent(u));
68        uf.unite(u, p);
69        if !uf.same(p, root) {
70            label[p] += 1;
71            heap.push((*uf.merge_data(p), p, label[p]));
72        }
73        next.swap(u, p);
74    }
75    let mut u = next[root];
76    ord.push(u);
77    while u != root {
78        u = next[u];
79        ord.push(u);
80    }
81    ord.reverse();
82    (cost, ord)
83}
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 73)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source

pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool

Source§

impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
where U: UnionStrategy, F: FindStrategy, M: UfMergeSpec, P: Group, H: UndoStrategy<UfCell<U, M, P>>,

Source

pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T>

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_1_b.rs (line 16)
6pub fn dsl_1_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            scan!(scanner, w: i64);
15            uf.unite_with(x, y, w);
16        } else if let Some(w) = uf.difference(x, y) {
17            writeln!(writer, "{}", w).ok();
18        } else {
19            writeln!(writer, "?").ok();
20        }
21    }
22}
Source

pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 475)
474    pub fn unite(&mut self, x: usize, y: usize) -> bool {
475        self.unite_with(x, y, P::unit())
476    }
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_1_b.rs (line 15)
6pub fn dsl_1_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            scan!(scanner, w: i64);
15            uf.unite_with(x, y, w);
16        } else if let Some(w) = uf.difference(x, y) {
17            writeln!(writer, "{}", w).ok();
18        } else {
19            writeln!(writer, "?").ok();
20        }
21    }
22}
Source

pub fn unite(&mut self, x: usize, y: usize) -> bool

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_1_a.rs (line 14)
6pub fn dsl_1_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            uf.unite(x, y);
15        } else {
16            writeln!(writer, "{}", (uf.same(x, y) as usize)).ok();
17        }
18    }
19}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 14)
6pub fn unionfind(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut uf = UnionFind::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, u, v);
13        if ty == 0 {
14            uf.unite(u, v);
15        } else {
16            writeln!(writer, "{}", uf.same(u, v) as usize).ok();
17        }
18    }
19}
crates/competitive/src/graph/minimum_spanning_tree.rs (line 14)
4    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
5    where
6        T: Ord,
7    {
8        let mut idx: Vec<_> = (0..self.edges_size()).collect();
9        idx.sort_by_key(weight);
10        let mut uf = UnionFind::new(self.vertices_size());
11        let mut res = vec![false; self.edges_size()];
12        for eid in idx.into_iter() {
13            let (u, v) = self[eid];
14            res[eid] = uf.unite(u, v);
15        }
16        res
17    }
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 68)
42pub fn solve_01_on_tree(
43    n: usize,
44    c01: impl Fn(usize) -> (usize, usize),
45    root: usize,
46    parent: impl Fn(usize) -> usize,
47) -> (usize, Vec<usize>) {
48    pub type UF<T, M> =
49        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
50    let mut cost = 0usize;
51    let c01 = |u| {
52        let c = c01(u);
53        Count01::new(c.0, c.1)
54    };
55    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
56        cost += x.cnt1 * y.cnt0;
57        *x += *y;
58    });
59    let mut label = vec![0; n];
60    let mut heap = BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u, 0)));
61    let mut next: Vec<_> = (0..n).collect();
62    let mut ord = Vec::with_capacity(n);
63    while let Some((_c, u, l)) = heap.pop() {
64        if label[u] != l {
65            continue;
66        }
67        let p = uf.find_root(parent(u));
68        uf.unite(u, p);
69        if !uf.same(p, root) {
70            label[p] += 1;
71            heap.push((*uf.merge_data(p), p, label[p]));
72        }
73        next.swap(u, p);
74    }
75    let mut u = next[root];
76    ord.push(u);
77    while u != root {
78        u = next[u];
79        ord.push(u);
80    }
81    ord.reverse();
82    (cost, ord)
83}
crates/competitive/src/graph/minimum_spanning_arborescence.rs (line 77)
5    pub fn minimum_spanning_arborescence<G, F>(
6        &self,
7        root: usize,
8        weight: F,
9    ) -> Option<(G::T, Vec<usize>)>
10    where
11        G: Group<T: Ord>,
12        F: Fn(usize) -> G::T,
13    {
14        struct WeightAct<G>(std::marker::PhantomData<fn() -> G>);
15        impl<G> MonoidAct for WeightAct<G>
16        where
17            G: Group,
18        {
19            type Key = (G::T, usize);
20            type Act = G::T;
21            type ActMonoid = G;
22
23            fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
24                (G::operate(&x.0, a), x.1)
25            }
26
27            fn act_assign(x: &mut Self::Key, a: &Self::Act) {
28                x.0 = G::operate(&x.0, a);
29            }
30        }
31        let mut uf = MergingUnionFind::new_with_merger(
32            self.vertices_size(),
33            |_| PairingHeap::<(G::T, usize), Less, WeightAct<G>>::default(),
34            |x, y| x.append(y),
35        );
36        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
37        state[root] = 2;
38        for (id, &(_, to)) in self.edges().enumerate() {
39            uf.merge_data_mut(to).push((weight(id), id));
40        }
41        let mut paredge = vec![0; self.edges_size()];
42        let mut ord = vec![];
43        let mut leaf = vec![self.edges_size(); self.vertices_size()];
44        let mut cycle = 0usize;
45        let mut acc = G::unit();
46        for mut cur in self.vertices() {
47            if state[cur] != 0 {
48                continue;
49            }
50            let mut path = vec![];
51            let mut ch = vec![];
52            while state[cur] != 2 {
53                path.push(cur);
54                state[cur] = 1;
55                let (w, eid) = {
56                    match uf.merge_data_mut(cur).pop() {
57                        Some((w, eid)) => (w, eid),
58                        None => return None,
59                    }
60                };
61                uf.merge_data_mut(cur).apply_all(G::inverse(&w));
62                acc = G::operate(&acc, &w);
63                ord.push(eid);
64                let (u, v) = self[eid];
65                if leaf[v] >= self.edges_size() {
66                    leaf[v] = eid;
67                }
68                while cycle > 0 {
69                    paredge[ch.pop().unwrap()] = eid;
70                    cycle -= 1;
71                }
72                ch.push(eid);
73                if state[uf.find_root(u)] == 1 {
74                    while let Some(t) = path.pop() {
75                        state[t] = 2;
76                        cycle += 1;
77                        if !uf.unite(u, t) {
78                            break;
79                        }
80                    }
81                    state[uf.find_root(u)] = 1;
82                }
83                cur = uf.find_root(u);
84            }
85            for u in path.into_iter() {
86                state[u] = 2;
87            }
88        }
89        let mut tree = vec![root; self.vertices_size()];
90        let mut used = vec![false; self.edges_size()];
91        for eid in ord.into_iter().rev() {
92            if !used[eid] {
93                let (u, v) = self[eid];
94                tree[v] = u;
95                let mut x = leaf[v];
96                while x != eid {
97                    used[x] = true;
98                    x = paredge[x];
99                }
100            }
101        }
102        Some((acc, tree))
103    }
Source§

impl<U, M, P, H> UnionFindBase<U, (), M, P, H>
where U: UnionStrategy, M: UfMergeSpec, P: Monoid, H: UndoStrategy<UfCell<U, M, P>>,

Source

pub fn undo(&mut self)

Trait Implementations§

Source§

impl<U, F, M, P, H> Clone for UnionFindBase<U, F, M, P, H>
where U: UnionStrategy<Info: Clone>, F: FindStrategy, M: UfMergeSpec<Data: Clone> + Clone, P: Monoid, H: UndoStrategy<UfCell<U, M, P>, History: Clone>,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<U, F, M, P, H> Debug for UnionFindBase<U, F, M, P, H>
where U: UnionStrategy<Info: Debug>, F: FindStrategy, M: UfMergeSpec<Data: Debug>, P: Monoid<T: Debug>, H: UndoStrategy<UfCell<U, M, P>, History: Debug>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<U, F, M, P, H> Freeze for UnionFindBase<U, F, M, P, H>
where M: Freeze, <H as UndoStrategy<UfCell<U, M, P>>>::History: Freeze,

§

impl<U, F, M, P, H> RefUnwindSafe for UnionFindBase<U, F, M, P, H>
where M: RefUnwindSafe, <H as UndoStrategy<UfCell<U, M, P>>>::History: RefUnwindSafe, <U as UnionStrategy>::Info: RefUnwindSafe, <M as UfMergeSpec>::Data: RefUnwindSafe, <P as Magma>::T: RefUnwindSafe,

§

impl<U, F, M, P, H> Send for UnionFindBase<U, F, M, P, H>
where M: Send, <H as UndoStrategy<UfCell<U, M, P>>>::History: Send, <U as UnionStrategy>::Info: Send, <M as UfMergeSpec>::Data: Send, <P as Magma>::T: Send,

§

impl<U, F, M, P, H> Sync for UnionFindBase<U, F, M, P, H>
where M: Sync, <H as UndoStrategy<UfCell<U, M, P>>>::History: Sync, <U as UnionStrategy>::Info: Sync, <M as UfMergeSpec>::Data: Sync, <P as Magma>::T: Sync,

§

impl<U, F, M, P, H> Unpin for UnionFindBase<U, F, M, P, H>
where M: Unpin, <H as UndoStrategy<UfCell<U, M, P>>>::History: Unpin, <U as UnionStrategy>::Info: Unpin, <M as UfMergeSpec>::Data: Unpin, <P as Magma>::T: Unpin,

§

impl<U, F, M, P, H> UnwindSafe for UnionFindBase<U, F, M, P, H>
where M: UnwindSafe, <H as UndoStrategy<UfCell<U, M, P>>>::History: UnwindSafe, <U as UnionStrategy>::Info: UnwindSafe, <M as UfMergeSpec>::Data: UnwindSafe, <P as Magma>::T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.