summaryrefslogtreecommitdiff
path: root/sources/merging_tables.py
diff options
context:
space:
mode:
Diffstat (limited to 'sources/merging_tables.py')
-rw-r--r--sources/merging_tables.py56
1 files changed, 56 insertions, 0 deletions
diff --git a/sources/merging_tables.py b/sources/merging_tables.py
new file mode 100644
index 0000000..985316e
--- /dev/null
+++ b/sources/merging_tables.py
@@ -0,0 +1,56 @@
+# python3
+
+
+class Database:
+ def __init__(self, row_counts):
+ self.row_counts = row_counts
+ self.max_row_count = max(row_counts)
+ n_tables = len(row_counts)
+ self.ranks = [1] * n_tables
+ self.parents = list(range(n_tables))
+ self.set_id = list(range(n_tables))
+
+ def find(self, i):
+ if i != self.parents[i]:
+ self.parents[i] = self.find(self.parents[i])
+ return self.parents[i]
+
+ def merge(self, src, dst):
+ real_dst = self.find(dst)
+ real_src = self.find(src)
+ if real_dst == real_src:
+ return
+ self.max_row_count = max(self.max_row_count,
+ self.row_counts[self.set_id[real_dst]] + self.row_counts[self.set_id[real_src]])
+ self.row_counts[real_dst] = self.row_counts[self.set_id[real_dst]] + self.row_counts[self.set_id[real_src]]
+ self.row_counts[real_src] = 0
+ self.set_id[real_src] = real_dst
+ self.set_id[real_dst] = real_dst
+ self.union(src, dst)
+
+ def union(self, src, dst):
+ destination_id = self.find(dst)
+ source_id = self.find(src)
+ if destination_id == source_id:
+ return
+ if self.ranks[destination_id] > self.ranks[source_id]:
+ self.parents[source_id] = destination_id
+ else:
+ self.parents[destination_id] = source_id
+ if self.ranks[destination_id] == self.ranks[source_id]:
+ self.ranks[source_id] = self.ranks[source_id] + 1
+
+
+def main():
+ n_tables, n_queries = map(int, input().split())
+ counts = list(map(int, input().split()))
+ assert len(counts) == n_tables
+ db = Database(counts)
+ for i in range(n_queries):
+ dst, src = map(int, input().split())
+ db.merge(dst - 1, src - 1)
+ print(db.max_row_count)
+
+
+if __name__ == "__main__":
+ main()