Simulates a sequence of merge operations with tables in a database.<\/p>\n
See code below<\/p>\n
<\/p>\n
# python3\r\nimport sys\r\n\r\nclass DisjointSet(object):\r\n \"\"\"Simulates a sequence of merge operations with tables in a database.\r\n \"\"\"\r\n def __init__(self, n, lines):\r\n \"\"\"Initializes a set for given n elements.\r\n\r\n Initially, the set consists of one element which is pointing to itself.\r\n Also during initialization the rank(tree's height) is assigned to 1\r\n for each set.\"\"\"\r\n\r\n self.n = n\r\n self.lines = [0] + lines\r\n self.rank = [0] * (n + 1)\r\n self.parent = list(range(0, n + 1))\r\n self.max = max(self.lines)\r\n\r\n def get_parent(self, x):\r\n \"\"\"Finds a set id (root of the tree) for element x and compresses path.\r\n \"\"\"\r\n parents_to_update = []\r\n\r\n # Find root.\r\n root = x\r\n while root != self.parent[root]:\r\n parents_to_update.append(self.parent[root])\r\n root = self.parent[root]\r\n\r\n # Compress path.\r\n for i in parents_to_update:\r\n self.parent[i] = root\r\n\r\n return root\r\n\r\n def merge(self, dest, src):\r\n \"\"\"Unions tables.\r\n\r\n During union updates rank's(tree's height) array.\"\"\"\r\n src_root = self.get_parent(src)\r\n dest_root = self.get_parent(dest)\r\n\r\n # Means the sets have been merged already.\r\n if src_root == dest_root:\r\n return\r\n\r\n if self.rank[src_root] >= self.rank[dest_root]:\r\n self.parent[src_root] = dest_root\r\n else:\r\n self.parent[dest_root] = src_root\r\n if self.rank[src_root] == self.rank[dest_root]:\r\n self.rank[src_root] += 1\r\n\r\n self.lines[dest_root] += self.lines[src_root]\r\n self.lines[src_root] = 0\r\n\r\n if self.max < self.lines[dest_root]:\r\n self.max = self.lines[dest_root]\r\n\r\n def get_max_lines(self):\r\n return self.max\r\n\r\n\r\nif __name__ == \"__main__\":\r\n n, m = map(int, sys.stdin.readline().split())\r\n lines = list(map(int, sys.stdin.readline().split()))\r\n\r\n ds = DisjointSet(n, lines)\r\n for i in range(m):\r\n destination, source = map(int, sys.stdin.readline().split())\r\n ds.merge(destination, source)\r\n print(ds.get_max_lines())<\/pre>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Simulates a sequence of merge operations with tables in a database. See code below<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30,33],"series":[],"class_list":["post-149","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code","tag-merging-tables"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=149"}],"version-history":[{"count":1,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/149\/revisions"}],"predecessor-version":[{"id":150,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/149\/revisions\/150"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=149"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}