library_checker/data_structure/
persistent_unionfind.rs

1use competitive::prelude::*;
2use competitive::{
3    data_structure::UndoableUnionFind,
4    graph::{DirectedSparseGraph, Graph},
5};
6
7#[verify::library_checker("persistent_unionfind")]
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}
library_checker/data_structure/persistent_unionfind.rs

library_checker/data_structure/
persistent_unionfind.rs
