Typescript union find with path compression, rank comparison and size tracking:

class UnionFind {
    par: {[key: number]: number} = {}
    rank: {[key: number]: number} = {}
    size: {[key: number]: number} = {}
    
    constructor(n: number) {
        for(let i = 1; i <= n; i++) this.par[i] = i, this.rank[i] = 1, this.size[i] = 1
    }
    
    getSize(x: number): number {
        const p = this.find(x)
        return this.size[p]
    }
    
    find(x: number): number {
       if (this.par[x] === x) {
           return x
       } else {
           this.par[x] = this.find(this.par[x])
           return this.par[x]
       }
    }
    
    union(n1: number, n2: number) {
        let p1 = this.find(n1), p2 = this.find(n2)
        if (p1 == p2) return true
        if (this.rank[p1] < this.rank[p2]) {
            this.par[p1] = p2
            this.size[p2] += this.size[p1]
        } else if (this.rank[p1] > this.rank[p2]) {
            this.par[p2] = p1
            this.size[p1] += this.size[p2]
        } else {
            this.par[p1] = p2
            this.rank[p2]++
            this.size[p2] += this.size[p1]
        }
    }
    
    print() {
        console.log('------')
        console.log('par', this.par)
        console.log('rank', this.rank)
        console.log('size', this.size)
    }
}

function main() {
    const [n, q] = readLine().split(' ').map(e => parseInt(e))
    const uf = new UnionFind(n)
    for (let k = 0; k < q; k++) {
        const [c, i, j] = readLine().split(' ')
        if (c === 'M') {
            uf.union(parseInt(i), parseInt(j))
        } else if (c === 'Q') {
            console.log(uf.getSize(parseInt(i)))
        }
    }
}

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.

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!

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!

Merging communities involves combining separate groups or forums into a unified entity. This process requires careful planning to ensure smooth integration of members, ecommerce photo editing content, and culture. Strategies may include transparent communication, facilitating introductions, and establishing common goals. It's crucial to address concerns, foster collaboration, and preserve the unique identities of each community. Effective merging can create a stronger, more diverse, and vibrant online community.