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>>,
{ /* private fields */ }

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/datastructure/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 13)
7    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
8    where
9        T: Ord,
10    {
11        let mut idx: Vec<_> = (0..self.edges_size()).collect();
12        idx.sort_by_key(weight);
13        let mut uf = UnionFind::new(self.vertices_size());
14        let mut res = vec![false; self.edges_size()];
15        for eid in idx.into_iter() {
16            let (u, v) = self[eid];
17            res[eid] = uf.unite(u, v);
18        }
19        res
20    }
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 50-53)
37pub fn solve_01_on_tree(
38    n: usize,
39    c01: impl Fn(usize) -> (usize, usize),
40    root: usize,
41    parent: impl Fn(usize) -> usize,
42) -> usize {
43    pub type UF<T, M> =
44        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
45    let mut cost = 0usize;
46    let c01 = |u| {
47        let c = c01(u);
48        Count01::new(c.0, c.1)
49    };
50    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
51        cost += x.cnt1 * y.cnt0;
52        *x += *y;
53    });
54    let mut heap = BTreeSet::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u)));
55    while let Some((_c, u)) = heap.pop_last() {
56        let p = uf.find_root(parent(u));
57        heap.remove(&(*uf.merge_data(p), p));
58        uf.unite(u, p);
59        if !uf.same(p, root) {
60            heap.insert((*uf.merge_data(p), p));
61        }
62    }
63    cost
64}
More examples
Hide additional examples
crates/competitive/src/graph/minimum_spanning_tree.rs (lines 40-51)
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
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

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/datastructure/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 59)
37pub fn solve_01_on_tree(
38    n: usize,
39    c01: impl Fn(usize) -> (usize, usize),
40    root: usize,
41    parent: impl Fn(usize) -> usize,
42) -> usize {
43    pub type UF<T, M> =
44        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
45    let mut cost = 0usize;
46    let c01 = |u| {
47        let c = c01(u);
48        Count01::new(c.0, c.1)
49    };
50    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
51        cost += x.cnt1 * y.cnt0;
52        *x += *y;
53    });
54    let mut heap = BTreeSet::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u)));
55    while let Some((_c, u)) = heap.pop_last() {
56        let p = uf.find_root(parent(u));
57        heap.remove(&(*uf.merge_data(p), p));
58        uf.unite(u, p);
59        if !uf.same(p, root) {
60            heap.insert((*uf.merge_data(p), p));
61        }
62    }
63    cost
64}
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 57)
37pub fn solve_01_on_tree(
38    n: usize,
39    c01: impl Fn(usize) -> (usize, usize),
40    root: usize,
41    parent: impl Fn(usize) -> usize,
42) -> usize {
43    pub type UF<T, M> =
44        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
45    let mut cost = 0usize;
46    let c01 = |u| {
47        let c = c01(u);
48        Count01::new(c.0, c.1)
49    };
50    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
51        cost += x.cnt1 * y.cnt0;
52        *x += *y;
53    });
54    let mut heap = BTreeSet::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u)));
55    while let Some((_c, u)) = heap.pop_last() {
56        let p = uf.find_root(parent(u));
57        heap.remove(&(*uf.merge_data(p), p));
58        uf.unite(u, p);
59        if !uf.same(p, root) {
60            heap.insert((*uf.merge_data(p), p));
61        }
62    }
63    cost
64}
Source

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

Examples found in repository?
crates/competitive/src/graph/minimum_spanning_tree.rs (line 55)
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
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 385)
383    pub fn find(&mut self, x: usize) -> (usize, P::T) {
384        let (parent_parent, parent_potential) = match &self.cells[x] {
385            UfCell::Child((parent, _)) => self.find(*parent),
386            UfCell::Root(_) => return (x, P::unit()),
387        };
388        let (parent, potential) = self.cells[x].child_mut().unwrap();
389        let potential = if F::CHENGE_ROOT {
390            *parent = parent_parent;
391            *potential = P::operate(&parent_potential, potential);
392            potential.clone()
393        } else {
394            P::operate(&parent_potential, potential)
395        };
396        (parent_parent, potential)
397    }
398
399    pub fn find_root(&mut self, x: usize) -> usize {
400        let (parent, parent_parent) = match &self.cells[x] {
401            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
402            UfCell::Root(_) => return x,
403        };
404        if F::CHENGE_ROOT {
405            let (cx, cp) = {
406                let ptr = self.cells.as_mut_ptr();
407                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
408            };
409            let (parent, potential) = cx.child_mut().unwrap();
410            *parent = parent_parent;
411            if let UfCell::Child((_, ppot)) = &cp {
412                *potential = P::operate(ppot, potential);
413            }
414        }
415        parent_parent
416    }
417
418    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
419        let (rx, potx) = self.find(x);
420        let ry = self.find_root(y);
421        if rx == ry || y != ry {
422            return false;
423        }
424        H::unite(&mut self.history, rx, ry, &self.cells);
425        {
426            let ptr = self.cells.as_mut_ptr();
427            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
428            self.merger
429                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
430        }
431        *self.root_info_mut(rx).unwrap() =
432            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
433        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
434        true
435    }
436}
437
438impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
439where
440    U: UnionStrategy,
441    F: FindStrategy,
442    M: UfMergeSpec,
443    P: Group,
444    H: UndoStrategy<UfCell<U, M, P>>,
445{
446    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
447        let (rx, potx) = self.find(x);
448        let (ry, poty) = self.find(y);
449        if rx == ry {
450            Some(P::operate(&P::inverse(&potx), &poty))
451        } else {
452            None
453        }
454    }
455
456    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
457        let (mut rx, potx) = self.find(x);
458        let (mut ry, poty) = self.find(y);
459        if rx == ry {
460            return false;
461        }
462        let mut xinfo = self.root_info(rx).unwrap();
463        let mut yinfo = self.root_info(ry).unwrap();
464        let inverse = !U::check_directoin(&xinfo, &yinfo);
465        let potential = if inverse {
466            P::rinv_operate(&poty, &P::operate(&potx, &potential))
467        } else {
468            P::operate(&potx, &P::rinv_operate(&potential, &poty))
469        };
470        if inverse {
471            swap(&mut rx, &mut ry);
472            swap(&mut xinfo, &mut yinfo);
473        }
474        H::unite(&mut self.history, rx, ry, &self.cells);
475        {
476            let ptr = self.cells.as_mut_ptr();
477            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
478            self.merger
479                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
480        }
481        *self.root_info_mut(rx).unwrap() = U::unite(&xinfo, &yinfo);
482        self.cells[ry] = UfCell::Child((rx, potential));
483        true
484    }
Source

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

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 323)
322    pub fn size(&mut self, x: usize) -> <UnionBySize as UnionStrategy>::Info {
323        let root = self.find_root(x);
324        self.root_info(root).unwrap()
325    }
326}
327
328impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
329where
330    U: UnionStrategy,
331    F: FindStrategy,
332    M: UfMergeSpec,
333    P: Monoid,
334    H: UndoStrategy<UfCell<U, M, P>>,
335{
336    fn root_info(&mut self, x: usize) -> Option<U::Info> {
337        match &self.cells[x] {
338            UfCell::Root((info, _)) => Some(info.clone()),
339            UfCell::Child(_) => None,
340        }
341    }
342
343    fn root_info_mut(&mut self, x: usize) -> Option<&mut U::Info> {
344        match &mut self.cells[x] {
345            UfCell::Root((info, _)) => Some(info),
346            UfCell::Child(_) => None,
347        }
348    }
349
350    pub fn same(&mut self, x: usize, y: usize) -> bool {
351        self.find_root(x) == self.find_root(y)
352    }
353
354    pub fn merge_data(&mut self, x: usize) -> &M::Data {
355        let root = self.find_root(x);
356        match &self.cells[root] {
357            UfCell::Root((_, data)) => data,
358            UfCell::Child(_) => unreachable!(),
359        }
360    }
361
362    pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data {
363        let root = self.find_root(x);
364        match &mut self.cells[root] {
365            UfCell::Root((_, data)) => data,
366            UfCell::Child(_) => unreachable!(),
367        }
368    }
369
370    pub fn roots(&self) -> impl Iterator<Item = usize> + '_ {
371        (0..self.cells.len()).filter(|&x| matches!(self.cells[x], UfCell::Root(_)))
372    }
373
374    pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>> {
375        let mut groups_map = HashMap::new();
376        for x in 0..self.cells.len() {
377            let r = self.find_root(x);
378            groups_map.entry(r).or_insert_with(Vec::new).push(x);
379        }
380        groups_map
381    }
382
383    pub fn find(&mut self, x: usize) -> (usize, P::T) {
384        let (parent_parent, parent_potential) = match &self.cells[x] {
385            UfCell::Child((parent, _)) => self.find(*parent),
386            UfCell::Root(_) => return (x, P::unit()),
387        };
388        let (parent, potential) = self.cells[x].child_mut().unwrap();
389        let potential = if F::CHENGE_ROOT {
390            *parent = parent_parent;
391            *potential = P::operate(&parent_potential, potential);
392            potential.clone()
393        } else {
394            P::operate(&parent_potential, potential)
395        };
396        (parent_parent, potential)
397    }
398
399    pub fn find_root(&mut self, x: usize) -> usize {
400        let (parent, parent_parent) = match &self.cells[x] {
401            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
402            UfCell::Root(_) => return x,
403        };
404        if F::CHENGE_ROOT {
405            let (cx, cp) = {
406                let ptr = self.cells.as_mut_ptr();
407                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
408            };
409            let (parent, potential) = cx.child_mut().unwrap();
410            *parent = parent_parent;
411            if let UfCell::Child((_, ppot)) = &cp {
412                *potential = P::operate(ppot, potential);
413            }
414        }
415        parent_parent
416    }
417
418    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
419        let (rx, potx) = self.find(x);
420        let ry = self.find_root(y);
421        if rx == ry || y != ry {
422            return false;
423        }
424        H::unite(&mut self.history, rx, ry, &self.cells);
425        {
426            let ptr = self.cells.as_mut_ptr();
427            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
428            self.merger
429                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
430        }
431        *self.root_info_mut(rx).unwrap() =
432            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
433        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
434        true
435    }
More examples
Hide additional examples
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 56)
37pub fn solve_01_on_tree(
38    n: usize,
39    c01: impl Fn(usize) -> (usize, usize),
40    root: usize,
41    parent: impl Fn(usize) -> usize,
42) -> usize {
43    pub type UF<T, M> =
44        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
45    let mut cost = 0usize;
46    let c01 = |u| {
47        let c = c01(u);
48        Count01::new(c.0, c.1)
49    };
50    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
51        cost += x.cnt1 * y.cnt0;
52        *x += *y;
53    });
54    let mut heap = BTreeSet::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u)));
55    while let Some((_c, u)) = heap.pop_last() {
56        let p = uf.find_root(parent(u));
57        heap.remove(&(*uf.merge_data(p), p));
58        uf.unite(u, p);
59        if !uf.same(p, root) {
60            heap.insert((*uf.merge_data(p), p));
61        }
62    }
63    cost
64}
crates/competitive/src/graph/minimum_spanning_tree.rs (line 93)
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
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 487)
486    pub fn unite(&mut self, x: usize, y: usize) -> bool {
487        self.unite_with(x, y, P::unit())
488    }
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/datastructure/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 17)
7    pub fn minimum_spanning_tree<T>(&self, weight: impl Fn(&usize) -> T) -> Vec<bool>
8    where
9        T: Ord,
10    {
11        let mut idx: Vec<_> = (0..self.edges_size()).collect();
12        idx.sort_by_key(weight);
13        let mut uf = UnionFind::new(self.vertices_size());
14        let mut res = vec![false; self.edges_size()];
15        for eid in idx.into_iter() {
16            let (u, v) = self[eid];
17            res[eid] = uf.unite(u, v);
18        }
19        res
20    }
21}
22
23#[codesnip::entry(
24    "minimum_spanning_arborescence",
25    include("algebra", "EdgeListGraph", "UnionFind")
26)]
27impl EdgeListGraph {
28    /// tarjan
29    pub fn minimum_spanning_arborescence<G, F>(
30        &self,
31        root: usize,
32        weight: F,
33    ) -> Option<(G::T, Vec<usize>)>
34    where
35        G: Group,
36        G::T: Ord,
37        F: Fn(usize) -> G::T,
38    {
39        use std::{cmp::Reverse, collections::BinaryHeap};
40        let mut uf = MergingUnionFind::new_with_merger(
41            self.vertices_size(),
42            |_| (BinaryHeap::new(), G::unit()),
43            |x, y| {
44                let ny = G::rinv_operate(&y.1, &x.1);
45                x.0.extend(
46                    (y.0)
47                        .drain()
48                        .map(|(Reverse(ref w), i)| (Reverse(G::operate(w, &ny)), i)),
49                )
50            },
51        );
52        let mut state = vec![0; self.vertices_size()]; // 0: unprocessed, 1: in process, 2: completed
53        state[root] = 2;
54        for (id, &(_, to)) in self.edges().enumerate() {
55            uf.merge_data_mut(to).0.push((Reverse(weight(id)), id));
56        }
57        let mut paredge = vec![0; self.edges_size()];
58        let mut ord = vec![];
59        let mut leaf = vec![self.edges_size(); self.vertices_size()];
60        let mut cycle = 0usize;
61        let mut acc = G::unit();
62        for mut cur in self.vertices() {
63            if state[cur] != 0 {
64                continue;
65            }
66            let mut path = vec![];
67            let mut ch = vec![];
68            while state[cur] != 2 {
69                path.push(cur);
70                state[cur] = 1;
71                let (w, eid) = {
72                    let (heap, lazy) = &mut uf.merge_data_mut(cur);
73                    match heap.pop() {
74                        Some((Reverse(w), eid)) => (G::operate(&w, lazy), eid),
75                        None => return None,
76                    }
77                };
78                {
79                    let curw = &mut uf.merge_data_mut(cur).1;
80                    *curw = G::rinv_operate(curw, &w);
81                }
82                acc = G::operate(&acc, &w);
83                ord.push(eid);
84                let (u, v) = self[eid];
85                if leaf[v] >= self.edges_size() {
86                    leaf[v] = eid;
87                }
88                while cycle > 0 {
89                    paredge[ch.pop().unwrap()] = eid;
90                    cycle -= 1;
91                }
92                ch.push(eid);
93                if state[uf.find_root(u)] == 1 {
94                    while let Some(t) = path.pop() {
95                        state[t] = 2;
96                        cycle += 1;
97                        if !uf.unite(u, t) {
98                            break;
99                        }
100                    }
101                    state[uf.find_root(u)] = 1;
102                }
103                cur = uf.find_root(u);
104            }
105            for u in path.into_iter() {
106                state[u] = 2;
107            }
108        }
109        let mut tree = vec![root; self.vertices_size()];
110        let mut used = vec![false; self.edges_size()];
111        for eid in ord.into_iter().rev() {
112            if !used[eid] {
113                let (u, v) = self[eid];
114                tree[v] = u;
115                let mut x = leaf[v];
116                while x != eid {
117                    used[x] = true;
118                    x = paredge[x];
119                }
120            }
121        }
122        Some((acc, tree))
123    }
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 58)
37pub fn solve_01_on_tree(
38    n: usize,
39    c01: impl Fn(usize) -> (usize, usize),
40    root: usize,
41    parent: impl Fn(usize) -> usize,
42) -> usize {
43    pub type UF<T, M> =
44        UnionFindBase<(), union_find::PathCompression, union_find::FnMerger<T, M>, (), ()>;
45    let mut cost = 0usize;
46    let c01 = |u| {
47        let c = c01(u);
48        Count01::new(c.0, c.1)
49    };
50    let mut uf = UF::new_with_merger(n, &c01, |x, y| {
51        cost += x.cnt1 * y.cnt0;
52        *x += *y;
53    });
54    let mut heap = BTreeSet::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u)));
55    while let Some((_c, u)) = heap.pop_last() {
56        let p = uf.find_root(parent(u));
57        heap.remove(&(*uf.merge_data(p), p));
58        uf.unite(u, p);
59        if !uf.same(p, root) {
60            heap.insert((*uf.merge_data(p), p));
61        }
62    }
63    cost
64}
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, F: FindStrategy, M: UfMergeSpec + Clone, P: Monoid, H: UndoStrategy<UfCell<U, M, P>>, U::Info: Clone, M::Data: Clone, H::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, F: FindStrategy, M: UfMergeSpec, P: Monoid, H: UndoStrategy<UfCell<U, M, P>>, U::Info: Debug, M::Data: Debug, P::T: Debug, H::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.