Great problem to understand the use of the Union-Find (Disjoint Set Union) data structure! Here’s my approach:

Approach: Union-Find Data Structure:

Use two arrays: parent and size. parent[i] points to the parent of node i. If parent[i] == i, i is the root of its set. size[i] keeps track of the size of the set where i is the root. Find Operation with Path Compression:

To find the root of a node, traverse up to its parent until reaching the root. Compress the path by making every node in the path point directly to the root. Union Operation by Size:

When merging two sets, always attach the smaller set under the larger set to keep the tree shallow. Update the size of the new root accordingly. Query Operation:

Use the find operation to determine the size of the community to which a person belongs. Example Code in Python: python Copy code class UnionFind: def init(self, n): self.parent = list(range(n)) self.size = [1] * n

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

def union(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)

    if rootP != rootQ:
        if self.size[rootP] < self.size[rootQ]:
            self.parent[rootP] = rootQ
            self.size[rootQ] += self.size[rootP]
        else:
            self.parent[rootQ] = rootP
            self.size[rootP] += self.size[rootQ]

def get_size(self, p):
    rootP = self.find(p)
    return self.size[rootP]

Reading input

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): query = data[index] if query == 'M': a = int(data[index + 1]) - 1 b = int(data[index + 2]) - 1 uf.union(a, b) index += 3 elif query == 'Q': a = int(data[index + 1]) - 1 print(uf.get_size(a)) index += 2 Explanation: Initialization: We initialize the Union-Find structure with n elements. Union Operation: For merging communities, we perform the union operation. Find Operation: For querying the size of the community, we use the find operation to locate the root and get the size. This solution efficiently handles both operations in nearly constant time, thanks to path compression and union by size. I hope this helps others understand and solve the problem more effectively!

Happy coding!