We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Disjoint Set
  4. Merging Communities
  5. Discussions

Merging Communities

  • shloombiequrat
     + 0 comments

    Optimized Union-Find Solution

    The Union-Find data structure is a powerful tool for managing disjoint sets efficiently. Here's a concise approach:

    1. Initialization:

      • Use parent and size arrays where each node starts as its own parent and each set has size 1.

    2. Path Compression:

      • Implement path compression in the find function to flatten the tree structure and speed up future operations.

    3. Union by Size:

      • Attach the smaller tree under the larger one during union operations to keep the structure balanced.

    4. Query Operation:

      • Retrieve the size of the set containing a node using the find function.

    Python 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)]

    Usage Example:

    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

    For more insights and advanced techniques on Union-Find and related algorithms, visit EduHQ.