diff options
Diffstat (limited to 'sources')
| -rw-r--r-- | sources/merging_tables.py | 56 |
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() |