mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
58 lines
1.2 KiB
Python
58 lines
1.2 KiB
Python
class UnionFind:
|
|
def __init__(self, nodes):
|
|
self.link = {node: None for node in nodes}
|
|
self.size = {node: 1 for node in nodes}
|
|
self.longest = 1
|
|
|
|
def find(self, x):
|
|
while self.link[x]:
|
|
x = self.link[x]
|
|
return x
|
|
|
|
def union(self, a, b):
|
|
a = self.find(a)
|
|
b = self.find(b)
|
|
if a == b:
|
|
return
|
|
|
|
if self.size[a] > self.size[b]:
|
|
a, b = b, a
|
|
self.link[a] = b
|
|
self.size[b] += self.size[a]
|
|
self.longest = max(self.size[b], self.longest)
|
|
|
|
def get_max(self):
|
|
return self.longest
|
|
|
|
|
|
class MaxSet:
|
|
def __init__(self, n):
|
|
self.uf = UnionFind([x for x in range(1, n + 1)])
|
|
|
|
def merge(self, a, b):
|
|
self.uf.union(a, b)
|
|
|
|
def get_max(self):
|
|
return self.uf.get_max()
|
|
|
|
|
|
if __name__ == "__main__":
|
|
max_set = MaxSet(5)
|
|
print(max_set.get_max()) # 1
|
|
|
|
max_set.merge(1, 2)
|
|
max_set.merge(3, 4)
|
|
max_set.merge(3, 5)
|
|
print(max_set.get_max()) # 3
|
|
|
|
max_set.merge(1, 5)
|
|
print(max_set.get_max()) # 5
|
|
|
|
max_set.merge(2, 3)
|
|
print(max_set.get_max()) # 5
|
|
|
|
max_set = MaxSet(10**5)
|
|
for i in range(2, 10**5 + 1):
|
|
max_set.merge(1, i)
|
|
print(max_set.get_max())
|