Source code for titan_pylib.data_structures.union_find.fully_retroactive_union_find
1from titan_pylib.data_structures.dynamic_connectivity.link_cut_tree import LinkCutTree
2
3
[docs]
4class FullyRetroactiveUnionFind:
5
6 def __init__(self, n: int, m: int) -> None:
7 """頂点数 ``n`` 、クエリ列の長さ ``m`` の ``FullyRetroactiveUnionFind`` を作ります。
8
9 ここで、クエリは `unite` のみです。
10
11 :math:`O(n+m)` です。
12
13 Args:
14 n (int): 頂点数です。
15 m (int): クエリ列の長さです。
16 """
17 m += 1
18 self.n: int = n
19 self.edge: list[tuple[int, int, int]] = [()] * m
20 self.node_pool: set[int] = set(range(n, n + m))
21 self.lct: LinkCutTree[int, None] = LinkCutTree(
22 n + m,
23 op=lambda s, t: s if s > t else t,
24 mapping=lambda f, s: -1,
25 composition=lambda f, g: None,
26 e=-1,
27 id=None,
28 )
29
[docs]
30 def unite(self, u: int, v: int, t: int) -> None:
31 """時刻 ``t`` のクエリを ``unite(u, v)`` にします。
32
33 償却 :math:`O(\\log{(n+m)})` です。
34
35 Args:
36 u (int): 集合の要素です。
37 v (int): 集合の要素です。
38 t (int): 時刻です。
39
40 Note:
41 ``disconnect`` を使用する場合、 ``u``, ``v`` が連結されていてはいけません。
42 """
43 node = self.node_pool.pop()
44 self.edge[t] = (u, v, node)
45 self.lct[node] = t
46 self.lct.merge(u, node)
47 self.lct.merge(node, v)
48
[docs]
49 def disconnect(self, t: int) -> None:
50 """時刻 ``t`` の連結クエリをなくして、そのクエリの2頂点を非連結にします。
51
52 償却 :math:`O(\\log{(n+m)})` です。
53
54 Args:
55 t (int): 時刻です。
56
57 Note:
58 時刻 ``t`` のクエリは連結クエリでないといけません。
59 """
60 assert self.edge[t] is not None
61 u, v, node = self.edge[t]
62 self.node_pool.add(node)
63 self.edge[t] = None
64 self.lct.split(u, node)
65 self.lct.split(node, v)
66
[docs]
67 def same(self, u: int, v: int, t: int) -> bool:
68 """時刻 ``t`` で ``u``, ``v`` の連結判定をします。
69
70 償却 :math:`O(\\log{(n+m)})` です。
71
72 Args:
73 u (int): 集合の要素です。
74 v (int): 集合の要素です。
75 t (int): 時刻です。
76
77 Returns:
78 bool:
79 """
80 if not self.lct.same(u, v):
81 return False
82 return self.lct.path_prod(u, v) <= t