Skip to main content

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<M::Data, P>>,
{
    cells: Vec<UfCell<M::Data, P>>,
    merger: M,
    history: H::History,
    _marker: PhantomData<fn() -> (U, F)>,
}

Fields§

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

Implementations§

Source§

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

Source

pub fn new(n: usize) -> Self

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_1_a.rs (line 15)
12pub fn dsl_1_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y } => {
20                uf.unite(x, y);
21            }
22            Query::Same { x, y } => {
23                pp!((uf.same(x, y) as usize));
24            }
25        }
26    }
27}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 15)
12pub fn unionfind(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { u, v } => {
20                uf.unite(u, v);
21            }
22            Query::Same { u, v } => {
23                pp!(uf.same(u, v) as usize);
24            }
25        }
26    }
27}
crates/aizu_online_judge/src/dsl/dsl_1_b.rs (line 15)
12pub fn dsl_1_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y, w } => {
20                uf.unite_with(x, y, w);
21            }
22            Query::Diff { x, y } => {
23                if let Some(w) = uf.difference(x, y) {
24                    pp!(w);
25                } else {
26                    pp!("?");
27                }
28            }
29        }
30    }
31}
crates/competitive/src/graph/minimum_spanning_tree.rs (line 18)
14    pub fn minimum_spanning_tree_from_sorted_edges(
15        &self,
16        edges: impl IntoIterator<Item = usize>,
17    ) -> Vec<bool> {
18        let mut uf = UnionFind::new(self.vertices_size());
19        let mut res = vec![false; self.edges_size()];
20        let mut selected = 0;
21        for eid in edges {
22            let (u, v) = self[eid];
23            res[eid] = uf.unite(u, v);
24            if res[eid] {
25                selected += 1;
26                if selected + 1 == self.vertices_size() {
27                    break;
28                }
29            }
30        }
31        res
32    }
crates/library_checker/src/graph/two_edge_connected_components.rs (line 13)
8pub fn two_edge_connected_components(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, edges: [(usize, usize); m]);
11    let graph = UndirectedSparseGraph::from_edges(n, edges);
12    let low_link = LowLink::new(&graph);
13    let mut uf = UnionFind::new(n);
14    for &(mut u, mut v) in &graph.edges {
15        if low_link.ord[u] > low_link.ord[v] {
16            std::mem::swap(&mut u, &mut v);
17        }
18        if low_link.ord[u] >= low_link.low[v] {
19            uf.unite(u, v);
20        }
21    }
22    let groups = uf.all_group_members();
23    pp!(groups.len());
24    for group in groups.into_values() {
25        pp!(group.len(), @it group);
26    }
27}
crates/library_checker/src/data_structure/unionfind_with_potential.rs (line 18)
15pub fn unionfind_with_potential(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q);
18    let mut uf = PotentializedUnionFind::<AdditiveOperation<M>>::new(n);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Unite { u, v, x } => {
23                if let Some(diff) = uf.difference(u, v) {
24                    pp!((diff == x) as u8);
25                } else {
26                    uf.unite_with(u, v, x);
27                    pp!("1");
28                }
29            }
30            Query::Diff { u, v } => {
31                if let Some(diff) = uf.difference(u, v) {
32                    pp!(diff);
33                } else {
34                    pp!("-1");
35                }
36            }
37        }
38    }
39}
Additional examples can be found in:
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<T, 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![0u32; n];
60    let mut heap =
61        BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u as u32, 0)));
62    let mut next: Vec<_> = (0..n).collect();
63    let mut ord = Vec::with_capacity(n);
64    while let Some((_c, u, l)) = heap.pop() {
65        let u = u as usize;
66        if label[u] != l {
67            continue;
68        }
69        let p = uf.find_root(parent(u));
70        uf.unite(u, p);
71        if p != root {
72            label[p] += 1;
73            heap.push((*uf.merge_data(p), p as u32, label[p]));
74        }
75        next.swap(u, p);
76    }
77    let mut u = next[root];
78    ord.push(u);
79    while u != root {
80        u = next[u];
81        ord.push(u);
82    }
83    ord.reverse();
84    (cost, ord)
85}
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<M::Data, P>>,

Source

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

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<M::Data, P>>,

Source

fn root_info(&self, x: usize) -> Option<u32>

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 355)
353    pub fn size(&mut self, x: usize) -> usize {
354        let root = self.find_root(x);
355        self.root_info(root).unwrap() as usize
356    }
357}
358
359impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
360where
361    U: UnionStrategy,
362    F: FindStrategy,
363    M: UfMergeSpec,
364    P: Monoid,
365    H: UndoStrategy<UfCell<M::Data, P>>,
366{
367    fn root_info(&self, x: usize) -> Option<u32> {
368        self.cells[x].root_info()
369    }
370
371    fn set_root_info(&mut self, x: usize, info: u32) {
372        self.cells[x].set_root_info(info);
373    }
374
375    pub fn same(&mut self, x: usize, y: usize) -> bool {
376        self.find_root(x) == self.find_root(y)
377    }
378
379    pub fn merge_data(&mut self, x: usize) -> &M::Data {
380        let root = self.find_root(x);
381        self.cells[root].data()
382    }
383
384    pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data {
385        let root = self.find_root(x);
386        self.cells[root].data_mut()
387    }
388
389    pub fn roots(&self) -> impl Iterator<Item = usize> + '_ {
390        (0..self.cells.len()).filter(|&x| self.cells[x].is_root())
391    }
392
393    pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>> {
394        let mut groups_map = HashMap::new();
395        for x in 0..self.cells.len() {
396            let r = self.find_root(x);
397            groups_map.entry(r).or_insert_with(Vec::new).push(x);
398        }
399        groups_map
400    }
401
402    pub fn find(&mut self, x: usize) -> (usize, P::T) {
403        let mut current = x;
404        let mut potential = P::unit();
405        while let Some(parent) = self.cells[current].parent() {
406            let current_potential = self.cells[current].potential.clone();
407            potential = P::operate(&current_potential, &potential);
408            if F::CHENGE_ROOT
409                && let Some(parent_parent) = self.cells[parent].parent()
410            {
411                let potential = P::operate(&self.cells[parent].potential, &current_potential);
412                self.cells[current].set_child(parent_parent, potential);
413            }
414            current = parent;
415        }
416        (current, potential)
417    }
418
419    pub fn find_root(&mut self, x: usize) -> usize {
420        let mut current = x;
421        while let Some(parent) = self.cells[current].parent() {
422            if F::CHENGE_ROOT
423                && let Some(parent_parent) = self.cells[parent].parent()
424            {
425                let potential = P::operate(
426                    &self.cells[parent].potential,
427                    &self.cells[current].potential,
428                );
429                self.cells[current].set_child(parent_parent, potential);
430            }
431            current = parent;
432        }
433        current
434    }
435
436    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
437        let (rx, potx) = self.find(x);
438        let ry = self.find_root(y);
439        if rx == ry || y != ry {
440            return false;
441        }
442        H::unite(&mut self.history, rx, ry, &self.cells);
443        {
444            let ptr = self.cells.as_mut_ptr();
445            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
446            self.merger.merge(cx.data_mut(), cy.data_mut());
447        }
448        let info = U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
449        self.set_root_info(rx, info);
450        self.cells[ry].set_child(rx, P::operate(&potx, &potential));
451        true
452    }
453}
454
455impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
456where
457    U: UnionStrategy,
458    F: FindStrategy,
459    M: UfMergeSpec,
460    P: Group,
461    H: UndoStrategy<UfCell<M::Data, P>>,
462{
463    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
464        let (rx, potx) = self.find(x);
465        let (ry, poty) = self.find(y);
466        if rx == ry {
467            Some(P::operate(&P::inverse(&potx), &poty))
468        } else {
469            None
470        }
471    }
472
473    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
474        let (mut rx, potx) = self.find(x);
475        let (mut ry, poty) = self.find(y);
476        if rx == ry {
477            return false;
478        }
479        let mut xinfo = self.root_info(rx).unwrap();
480        let mut yinfo = self.root_info(ry).unwrap();
481        let inverse = !U::check_directoin(&xinfo, &yinfo);
482        let potential = if inverse {
483            P::rinv_operate(&poty, &P::operate(&potx, &potential))
484        } else {
485            P::operate(&potx, &P::rinv_operate(&potential, &poty))
486        };
487        if inverse {
488            swap(&mut rx, &mut ry);
489            swap(&mut xinfo, &mut yinfo);
490        }
491        H::unite(&mut self.history, rx, ry, &self.cells);
492        {
493            let ptr = self.cells.as_mut_ptr();
494            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
495            self.merger.merge(cx.data_mut(), cy.data_mut());
496        }
497        self.set_root_info(rx, U::unite(&xinfo, &yinfo));
498        self.cells[ry].set_child(rx, potential);
499        true
500    }
Source

fn set_root_info(&mut self, x: usize, info: u32)

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 449)
436    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
437        let (rx, potx) = self.find(x);
438        let ry = self.find_root(y);
439        if rx == ry || y != ry {
440            return false;
441        }
442        H::unite(&mut self.history, rx, ry, &self.cells);
443        {
444            let ptr = self.cells.as_mut_ptr();
445            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
446            self.merger.merge(cx.data_mut(), cy.data_mut());
447        }
448        let info = U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
449        self.set_root_info(rx, info);
450        self.cells[ry].set_child(rx, P::operate(&potx, &potential));
451        true
452    }
453}
454
455impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
456where
457    U: UnionStrategy,
458    F: FindStrategy,
459    M: UfMergeSpec,
460    P: Group,
461    H: UndoStrategy<UfCell<M::Data, P>>,
462{
463    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
464        let (rx, potx) = self.find(x);
465        let (ry, poty) = self.find(y);
466        if rx == ry {
467            Some(P::operate(&P::inverse(&potx), &poty))
468        } else {
469            None
470        }
471    }
472
473    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
474        let (mut rx, potx) = self.find(x);
475        let (mut ry, poty) = self.find(y);
476        if rx == ry {
477            return false;
478        }
479        let mut xinfo = self.root_info(rx).unwrap();
480        let mut yinfo = self.root_info(ry).unwrap();
481        let inverse = !U::check_directoin(&xinfo, &yinfo);
482        let potential = if inverse {
483            P::rinv_operate(&poty, &P::operate(&potx, &potential))
484        } else {
485            P::operate(&potx, &P::rinv_operate(&potential, &poty))
486        };
487        if inverse {
488            swap(&mut rx, &mut ry);
489            swap(&mut xinfo, &mut yinfo);
490        }
491        H::unite(&mut self.history, rx, ry, &self.cells);
492        {
493            let ptr = self.cells.as_mut_ptr();
494            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
495            self.merger.merge(cx.data_mut(), cy.data_mut());
496        }
497        self.set_root_info(rx, U::unite(&xinfo, &yinfo));
498        self.cells[ry].set_child(rx, potential);
499        true
500    }
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 23)
12pub fn dsl_1_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y } => {
20                uf.unite(x, y);
21            }
22            Query::Same { x, y } => {
23                pp!((uf.same(x, y) as usize));
24            }
25        }
26    }
27}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 23)
12pub fn unionfind(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { u, v } => {
20                uf.unite(u, v);
21            }
22            Query::Same { u, v } => {
23                pp!(uf.same(u, v) as usize);
24            }
25        }
26    }
27}
crates/library_checker/src/data_structure/persistent_unionfind.rs (line 42)
8pub fn persistent_unionfind(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, queries: [(u8, i32, u32, u32); q]);
11    let children = DirectedSparseGraph::from_edges(
12        q + 1,
13        queries
14            .iter()
15            .enumerate()
16            .map(|(i, &(_, k, _, _))| ((k + 1) as usize, i + 1))
17            .collect(),
18    );
19    let mut uf = UndoableUnionFind::new(n);
20    let mut ans = vec![false; q];
21    let mut stack: Vec<_> = children
22        .neighbors(0)
23        .map(|edge| (edge.to as u32 - 1, false))
24        .collect();
25    while let Some((i, undo)) = stack.pop() {
26        let i = i as usize;
27        if undo {
28            uf.undo();
29            continue;
30        }
31        let (t, _, u, v) = queries[i];
32        if t == 0 {
33            if uf.unite(u as usize, v as usize) {
34                stack.push((i as u32, true));
35            }
36            stack.extend(
37                children
38                    .neighbors(i + 1)
39                    .map(|edge| (edge.to as u32 - 1, false)),
40            );
41        } else {
42            ans[i] = uf.same(u as usize, v as usize);
43        }
44    }
45    for (i, &(t, _, _, _)) in queries.iter().enumerate() {
46        if t == 1 {
47            pp!(ans[i] as u8);
48        }
49    }
50}
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 73)
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![0u32; n];
60    let mut heap =
61        BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u as u32, 0)));
62    let mut next: Vec<_> = (0..n).collect();
63    let mut ord = Vec::with_capacity(n);
64    while let Some((_c, u, l)) = heap.pop() {
65        let u = u as usize;
66        if label[u] != l {
67            continue;
68        }
69        let p = uf.find_root(parent(u));
70        uf.unite(u, p);
71        if p != root {
72            label[p] += 1;
73            heap.push((*uf.merge_data(p), p as u32, label[p]));
74        }
75        next.swap(u, p);
76    }
77    let mut u = next[root];
78    ord.push(u);
79    while u != root {
80        u = next[u];
81        ord.push(u);
82    }
83    ord.reverse();
84    (cost, ord)
85}
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>>

Examples found in repository?
crates/library_checker/src/graph/two_edge_connected_components.rs (line 22)
8pub fn two_edge_connected_components(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, edges: [(usize, usize); m]);
11    let graph = UndirectedSparseGraph::from_edges(n, edges);
12    let low_link = LowLink::new(&graph);
13    let mut uf = UnionFind::new(n);
14    for &(mut u, mut v) in &graph.edges {
15        if low_link.ord[u] > low_link.ord[v] {
16            std::mem::swap(&mut u, &mut v);
17        }
18        if low_link.ord[u] >= low_link.low[v] {
19            uf.unite(u, v);
20        }
21    }
22    let groups = uf.all_group_members();
23    pp!(groups.len());
24    for group in groups.into_values() {
25        pp!(group.len(), @it group);
26    }
27}
Source

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

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 437)
436    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
437        let (rx, potx) = self.find(x);
438        let ry = self.find_root(y);
439        if rx == ry || y != ry {
440            return false;
441        }
442        H::unite(&mut self.history, rx, ry, &self.cells);
443        {
444            let ptr = self.cells.as_mut_ptr();
445            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
446            self.merger.merge(cx.data_mut(), cy.data_mut());
447        }
448        let info = U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
449        self.set_root_info(rx, info);
450        self.cells[ry].set_child(rx, P::operate(&potx, &potential));
451        true
452    }
453}
454
455impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
456where
457    U: UnionStrategy,
458    F: FindStrategy,
459    M: UfMergeSpec,
460    P: Group,
461    H: UndoStrategy<UfCell<M::Data, P>>,
462{
463    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
464        let (rx, potx) = self.find(x);
465        let (ry, poty) = self.find(y);
466        if rx == ry {
467            Some(P::operate(&P::inverse(&potx), &poty))
468        } else {
469            None
470        }
471    }
472
473    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
474        let (mut rx, potx) = self.find(x);
475        let (mut ry, poty) = self.find(y);
476        if rx == ry {
477            return false;
478        }
479        let mut xinfo = self.root_info(rx).unwrap();
480        let mut yinfo = self.root_info(ry).unwrap();
481        let inverse = !U::check_directoin(&xinfo, &yinfo);
482        let potential = if inverse {
483            P::rinv_operate(&poty, &P::operate(&potx, &potential))
484        } else {
485            P::operate(&potx, &P::rinv_operate(&potential, &poty))
486        };
487        if inverse {
488            swap(&mut rx, &mut ry);
489            swap(&mut xinfo, &mut yinfo);
490        }
491        H::unite(&mut self.history, rx, ry, &self.cells);
492        {
493            let ptr = self.cells.as_mut_ptr();
494            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
495            self.merger.merge(cx.data_mut(), cy.data_mut());
496        }
497        self.set_root_info(rx, U::unite(&xinfo, &yinfo));
498        self.cells[ry].set_child(rx, potential);
499        true
500    }
Source

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

Examples found in repository?
crates/competitive/src/data_structure/union_find.rs (line 354)
353    pub fn size(&mut self, x: usize) -> usize {
354        let root = self.find_root(x);
355        self.root_info(root).unwrap() as usize
356    }
357}
358
359impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
360where
361    U: UnionStrategy,
362    F: FindStrategy,
363    M: UfMergeSpec,
364    P: Monoid,
365    H: UndoStrategy<UfCell<M::Data, P>>,
366{
367    fn root_info(&self, x: usize) -> Option<u32> {
368        self.cells[x].root_info()
369    }
370
371    fn set_root_info(&mut self, x: usize, info: u32) {
372        self.cells[x].set_root_info(info);
373    }
374
375    pub fn same(&mut self, x: usize, y: usize) -> bool {
376        self.find_root(x) == self.find_root(y)
377    }
378
379    pub fn merge_data(&mut self, x: usize) -> &M::Data {
380        let root = self.find_root(x);
381        self.cells[root].data()
382    }
383
384    pub fn merge_data_mut(&mut self, x: usize) -> &mut M::Data {
385        let root = self.find_root(x);
386        self.cells[root].data_mut()
387    }
388
389    pub fn roots(&self) -> impl Iterator<Item = usize> + '_ {
390        (0..self.cells.len()).filter(|&x| self.cells[x].is_root())
391    }
392
393    pub fn all_group_members(&mut self) -> HashMap<usize, Vec<usize>> {
394        let mut groups_map = HashMap::new();
395        for x in 0..self.cells.len() {
396            let r = self.find_root(x);
397            groups_map.entry(r).or_insert_with(Vec::new).push(x);
398        }
399        groups_map
400    }
401
402    pub fn find(&mut self, x: usize) -> (usize, P::T) {
403        let mut current = x;
404        let mut potential = P::unit();
405        while let Some(parent) = self.cells[current].parent() {
406            let current_potential = self.cells[current].potential.clone();
407            potential = P::operate(&current_potential, &potential);
408            if F::CHENGE_ROOT
409                && let Some(parent_parent) = self.cells[parent].parent()
410            {
411                let potential = P::operate(&self.cells[parent].potential, &current_potential);
412                self.cells[current].set_child(parent_parent, potential);
413            }
414            current = parent;
415        }
416        (current, potential)
417    }
418
419    pub fn find_root(&mut self, x: usize) -> usize {
420        let mut current = x;
421        while let Some(parent) = self.cells[current].parent() {
422            if F::CHENGE_ROOT
423                && let Some(parent_parent) = self.cells[parent].parent()
424            {
425                let potential = P::operate(
426                    &self.cells[parent].potential,
427                    &self.cells[current].potential,
428                );
429                self.cells[current].set_child(parent_parent, potential);
430            }
431            current = parent;
432        }
433        current
434    }
435
436    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
437        let (rx, potx) = self.find(x);
438        let ry = self.find_root(y);
439        if rx == ry || y != ry {
440            return false;
441        }
442        H::unite(&mut self.history, rx, ry, &self.cells);
443        {
444            let ptr = self.cells.as_mut_ptr();
445            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
446            self.merger.merge(cx.data_mut(), cy.data_mut());
447        }
448        let info = U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
449        self.set_root_info(rx, info);
450        self.cells[ry].set_child(rx, P::operate(&potx, &potential));
451        true
452    }
More examples
Hide additional examples
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![0u32; n];
60    let mut heap =
61        BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u as u32, 0)));
62    let mut next: Vec<_> = (0..n).collect();
63    let mut ord = Vec::with_capacity(n);
64    while let Some((_c, u, l)) = heap.pop() {
65        let u = u as usize;
66        if label[u] != l {
67            continue;
68        }
69        let p = uf.find_root(parent(u));
70        uf.unite(u, p);
71        if p != root {
72            label[p] += 1;
73            heap.push((*uf.merge_data(p), p as u32, label[p]));
74        }
75        next.swap(u, p);
76    }
77    let mut u = next[root];
78    ord.push(u);
79    while u != root {
80        u = next[u];
81        ord.push(u);
82    }
83    ord.reverse();
84    (cost, ord)
85}
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<M::Data, 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 23)
12pub fn dsl_1_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y, w } => {
20                uf.unite_with(x, y, w);
21            }
22            Query::Diff { x, y } => {
23                if let Some(w) = uf.difference(x, y) {
24                    pp!(w);
25                } else {
26                    pp!("?");
27                }
28            }
29        }
30    }
31}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind_with_potential.rs (line 23)
15pub fn unionfind_with_potential(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q);
18    let mut uf = PotentializedUnionFind::<AdditiveOperation<M>>::new(n);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Unite { u, v, x } => {
23                if let Some(diff) = uf.difference(u, v) {
24                    pp!((diff == x) as u8);
25                } else {
26                    uf.unite_with(u, v, x);
27                    pp!("1");
28                }
29            }
30            Query::Diff { u, v } => {
31                if let Some(diff) = uf.difference(u, v) {
32                    pp!(diff);
33                } else {
34                    pp!("-1");
35                }
36            }
37        }
38    }
39}
crates/library_checker/src/data_structure/unionfind_with_potential_non_commutative_group.rs (line 45)
37pub fn unionfind_with_potential_non_commutative_group(reader: impl Read, writer: impl Write) {
38    prepare_io!(reader, writer);
39    sc!(n, q);
40    let mut uf = PotentializedUnionFind::<Sl2>::new(n);
41    for _ in 0..q {
42        sc!(query: Query);
43        match query {
44            Query::Unite { u, v, x } => {
45                if let Some(diff) = uf.difference(v, u) {
46                    pp!((diff == x) as u8);
47                } else {
48                    uf.unite_with(v, u, x);
49                    pp!("1");
50                }
51            }
52            Query::Diff { u, v } => {
53                if let Some(diff) = uf.difference(v, u) {
54                    pp!(@it diff.into_iter().flatten());
55                } else {
56                    pp!("-1");
57                }
58            }
59        }
60    }
61}
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 503)
502    pub fn unite(&mut self, x: usize, y: usize) -> bool {
503        self.unite_with(x, y, P::unit())
504    }
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_1_b.rs (line 20)
12pub fn dsl_1_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = PotentializedUnionFind::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y, w } => {
20                uf.unite_with(x, y, w);
21            }
22            Query::Diff { x, y } => {
23                if let Some(w) = uf.difference(x, y) {
24                    pp!(w);
25                } else {
26                    pp!("?");
27                }
28            }
29        }
30    }
31}
crates/library_checker/src/data_structure/unionfind_with_potential.rs (line 26)
15pub fn unionfind_with_potential(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q);
18    let mut uf = PotentializedUnionFind::<AdditiveOperation<M>>::new(n);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Unite { u, v, x } => {
23                if let Some(diff) = uf.difference(u, v) {
24                    pp!((diff == x) as u8);
25                } else {
26                    uf.unite_with(u, v, x);
27                    pp!("1");
28                }
29            }
30            Query::Diff { u, v } => {
31                if let Some(diff) = uf.difference(u, v) {
32                    pp!(diff);
33                } else {
34                    pp!("-1");
35                }
36            }
37        }
38    }
39}
crates/library_checker/src/data_structure/unionfind_with_potential_non_commutative_group.rs (line 48)
37pub fn unionfind_with_potential_non_commutative_group(reader: impl Read, writer: impl Write) {
38    prepare_io!(reader, writer);
39    sc!(n, q);
40    let mut uf = PotentializedUnionFind::<Sl2>::new(n);
41    for _ in 0..q {
42        sc!(query: Query);
43        match query {
44            Query::Unite { u, v, x } => {
45                if let Some(diff) = uf.difference(v, u) {
46                    pp!((diff == x) as u8);
47                } else {
48                    uf.unite_with(v, u, x);
49                    pp!("1");
50                }
51            }
52            Query::Diff { u, v } => {
53                if let Some(diff) = uf.difference(v, u) {
54                    pp!(@it diff.into_iter().flatten());
55                } else {
56                    pp!("-1");
57                }
58            }
59        }
60    }
61}
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 20)
12pub fn dsl_1_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { x, y } => {
20                uf.unite(x, y);
21            }
22            Query::Same { x, y } => {
23                pp!((uf.same(x, y) as usize));
24            }
25        }
26    }
27}
More examples
Hide additional examples
crates/library_checker/src/data_structure/unionfind.rs (line 20)
12pub fn unionfind(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut uf = UnionFind::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Unite { u, v } => {
20                uf.unite(u, v);
21            }
22            Query::Same { u, v } => {
23                pp!(uf.same(u, v) as usize);
24            }
25        }
26    }
27}
crates/competitive/src/graph/minimum_spanning_tree.rs (line 23)
14    pub fn minimum_spanning_tree_from_sorted_edges(
15        &self,
16        edges: impl IntoIterator<Item = usize>,
17    ) -> Vec<bool> {
18        let mut uf = UnionFind::new(self.vertices_size());
19        let mut res = vec![false; self.edges_size()];
20        let mut selected = 0;
21        for eid in edges {
22            let (u, v) = self[eid];
23            res[eid] = uf.unite(u, v);
24            if res[eid] {
25                selected += 1;
26                if selected + 1 == self.vertices_size() {
27                    break;
28                }
29            }
30        }
31        res
32    }
crates/library_checker/src/graph/two_edge_connected_components.rs (line 19)
8pub fn two_edge_connected_components(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, edges: [(usize, usize); m]);
11    let graph = UndirectedSparseGraph::from_edges(n, edges);
12    let low_link = LowLink::new(&graph);
13    let mut uf = UnionFind::new(n);
14    for &(mut u, mut v) in &graph.edges {
15        if low_link.ord[u] > low_link.ord[v] {
16            std::mem::swap(&mut u, &mut v);
17        }
18        if low_link.ord[u] >= low_link.low[v] {
19            uf.unite(u, v);
20        }
21    }
22    let groups = uf.all_group_members();
23    pp!(groups.len());
24    for group in groups.into_values() {
25        pp!(group.len(), @it group);
26    }
27}
crates/competitive/src/graph/steiner_tree.rs (line 276)
253    pub fn edges_from_source(&self, source: G::Vertex) -> Option<Vec<G::Label>> {
254        if self.dp.is_empty() {
255            return Some(vec![]);
256        }
257        if self.minimum_from_source(source) == S::inf() {
258            return None;
259        }
260        let graph = self.graph;
261        let mut index = graph.construct_vmap(|| 0usize);
262        for (i, u) in graph.vertices().enumerate() {
263            *graph.vmap_get_mut(&mut index, u) = i;
264        }
265        let mut uf = UnionFind::new(graph.vsize());
266        let mut edges = vec![];
267        let mut stack = vec![(self.dp.len() - 1, source)];
268        while let Some((bit, u)) = stack.pop() {
269            match graph.vmap_get(&self.parent[bit], u) {
270                SteinerTreeParent::None => {}
271                &SteinerTreeParent::Split(sub) => {
272                    stack.push((sub, u));
273                    stack.push((bit ^ sub, u));
274                }
275                SteinerTreeParent::Edge(v, label) => {
276                    if uf.unite(*graph.vmap_get(&index, u), *graph.vmap_get(&index, *v)) {
277                        edges.push(label.clone());
278                    }
279                    stack.push((bit, *v));
280                }
281            }
282        }
283        Some(edges)
284    }
crates/competitive/src/algorithm/solve_01_on_tree.rs (line 70)
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![0u32; n];
60    let mut heap =
61        BinaryHeap::from_iter((0..n).filter(|&u| u != root).map(|u| (c01(u), u as u32, 0)));
62    let mut next: Vec<_> = (0..n).collect();
63    let mut ord = Vec::with_capacity(n);
64    while let Some((_c, u, l)) = heap.pop() {
65        let u = u as usize;
66        if label[u] != l {
67            continue;
68        }
69        let p = uf.find_root(parent(u));
70        uf.unite(u, p);
71        if p != root {
72            label[p] += 1;
73            heap.push((*uf.merge_data(p), p as u32, label[p]));
74        }
75        next.swap(u, p);
76    }
77    let mut u = next[root];
78    ord.push(u);
79    while u != root {
80        u = next[u];
81        ord.push(u);
82    }
83    ord.reverse();
84    (cost, ord)
85}
Additional examples can be found in:
Source§

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

Source

pub fn undo(&mut self)

Examples found in repository?
crates/library_checker/src/data_structure/persistent_unionfind.rs (line 28)
8pub fn persistent_unionfind(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, queries: [(u8, i32, u32, u32); q]);
11    let children = DirectedSparseGraph::from_edges(
12        q + 1,
13        queries
14            .iter()
15            .enumerate()
16            .map(|(i, &(_, k, _, _))| ((k + 1) as usize, i + 1))
17            .collect(),
18    );
19    let mut uf = UndoableUnionFind::new(n);
20    let mut ans = vec![false; q];
21    let mut stack: Vec<_> = children
22        .neighbors(0)
23        .map(|edge| (edge.to as u32 - 1, false))
24        .collect();
25    while let Some((i, undo)) = stack.pop() {
26        let i = i as usize;
27        if undo {
28            uf.undo();
29            continue;
30        }
31        let (t, _, u, v) = queries[i];
32        if t == 0 {
33            if uf.unite(u as usize, v as usize) {
34                stack.push((i as u32, true));
35            }
36            stack.extend(
37                children
38                    .neighbors(i + 1)
39                    .map(|edge| (edge.to as u32 - 1, false)),
40            );
41        } else {
42            ans[i] = uf.same(u as usize, v as usize);
43        }
44    }
45    for (i, &(t, _, _, _)) in queries.iter().enumerate() {
46        if t == 1 {
47            pp!(ans[i] as u8);
48        }
49    }
50}

Trait Implementations§

Source§

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

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · 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<Data: Debug>, P: Monoid<T: Debug>, H: UndoStrategy<UfCell<M::Data, 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 Vec<UfCell<<M as UfMergeSpec>::Data, P>>: Freeze, M: Freeze, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: Freeze, PhantomData<fn() -> (U, F)>: Freeze,

§

impl<U, F, M, P, H> RefUnwindSafe for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: RefUnwindSafe, M: RefUnwindSafe, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: RefUnwindSafe, PhantomData<fn() -> (U, F)>: RefUnwindSafe,

§

impl<U, F, M, P, H> Send for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: Send, M: Send, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: Send, PhantomData<fn() -> (U, F)>: Send,

§

impl<U, F, M, P, H> Sync for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: Sync, M: Sync, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: Sync, PhantomData<fn() -> (U, F)>: Sync,

§

impl<U, F, M, P, H> Unpin for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: Unpin, M: Unpin, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: Unpin, PhantomData<fn() -> (U, F)>: Unpin,

§

impl<U, F, M, P, H> UnsafeUnpin for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: UnsafeUnpin, M: UnsafeUnpin, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: UnsafeUnpin, PhantomData<fn() -> (U, F)>: UnsafeUnpin,

§

impl<U, F, M, P, H> UnwindSafe for UnionFindBase<U, F, M, P, H>
where Vec<UfCell<<M as UfMergeSpec>::Data, P>>: UnwindSafe, M: UnwindSafe, <H as UndoStrategy<UfCell<<M as UfMergeSpec>::Data, P>>>::History: UnwindSafe, PhantomData<fn() -> (U, F)>: 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> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

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 = !

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

fn try_from(value: U) -> Result<T, !>

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.