Simulates a sequence of merge operations with tables in a database.
See code below
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# python3 import sys class DisjointSet(object): """Simulates a sequence of merge operations with tables in a database. """ def __init__(self, n, lines): """Initializes a set for given n elements. Initially, the set consists of one element which is pointing to itself. Also during initialization the rank(tree's height) is assigned to 1 for each set.""" self.n = n self.lines = [0] + lines self.rank = [0] * (n + 1) self.parent = list(range(0, n + 1)) self.max = max(self.lines) def get_parent(self, x): """Finds a set id (root of the tree) for element x and compresses path. """ parents_to_update = [] # Find root. root = x while root != self.parent[root]: parents_to_update.append(self.parent[root]) root = self.parent[root] # Compress path. for i in parents_to_update: self.parent[i] = root return root def merge(self, dest, src): """Unions tables. During union updates rank's(tree's height) array.""" src_root = self.get_parent(src) dest_root = self.get_parent(dest) # Means the sets have been merged already. if src_root == dest_root: return if self.rank[src_root] >= self.rank[dest_root]: self.parent[src_root] = dest_root else: self.parent[dest_root] = src_root if self.rank[src_root] == self.rank[dest_root]: self.rank[src_root] += 1 self.lines[dest_root] += self.lines[src_root] self.lines[src_root] = 0 if self.max < self.lines[dest_root]: self.max = self.lines[dest_root] def get_max_lines(self): return self.max if __name__ == "__main__": n, m = map(int, sys.stdin.readline().split()) lines = list(map(int, sys.stdin.readline().split())) ds = DisjointSet(n, lines) for i in range(m): destination, source = map(int, sys.stdin.readline().split()) ds.merge(destination, source) print(ds.get_max_lines()) |
Leave a Reply