Optimized Solution with Union-Find Data Structure

This problem is a perfect application of the Union-Find (or Disjoint Set Union) data structure, which helps efficiently manage and merge disjoint sets. Here’s a breakdown of the approach I used:

Strategy: Union-Find Initialization:

Use two arrays: parent to store the parent of each node, and size to store the size of each set. Initially, each node is its own parent, and each set has a size of 1. Path Compression in Find Operation:

Implement the find function with path compression to flatten the structure, making future operations faster. Union by Size:

During the union operation, always attach the smaller tree under the root of the larger tree to maintain a balanced structure. Query Operation:

Use the find function to determine the root of a node and return the size of the set that the root belongs to. Python Implementation: python Copy code class UnionFind: def init(self, n): self.parent = list(range(n)) self.size = [1] * n

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # path compression
    return self.parent[x]

def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)

    if rootX != rootY:
        if self.size[rootX] < self.size[rootY]:
            self.parent[rootX] = rootY
            self.size[rootY] += self.size[rootX]
        else:
            self.parent[rootY] = rootX
            self.size[rootX] += self.size[rootY]

def get_size(self, x):
    return self.size[self.find(x)]

import sys input = sys.stdin.read data = input().split()

n = int(data[0]) q = int(data[1])

uf = UnionFind(n)

index = 2 for _ in range(q): if data[index] == 'M': x = int(data[index + 1]) - 1 y = int(data[index + 2]) - 1 uf.union(x, y) index += 3 elif data[index] == 'Q': x = int(data[index + 1]) - 1 print(uf.get_size(x)) index += 2 Explanation: Initialization: Create a Union-Find structure for n elements, where each element initially points to itself. Union Operation: When merging two communities, connect the roots and update the sizes accordingly. Find Operation: For size queries, find the root of the element and return the size of the set associated with the root. This solution ensures that both union and find operations are efficient, nearly constant time due to path compression and union by size. It’s a robust approach to handle the merging and querying of communities effectively.

Hope this helps others in understanding and solving the problem!

Happy coding!