You are viewing a single comment's thread. Return to all comments →
Optimized Union-Find Solution
The Union-Find data structure is a powerful tool for managing disjoint sets efficiently. Here's a concise approach:
Initialization:
parent
size
Path Compression:
find
Union by Size:
Query Operation:
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.
What happens if the input includes already connected nodes? Does this handle that efficiently?
Seems like cookies are disabled on this browser, please enable them to open this website
I agree to HackerRank's Terms of Service and Privacy Policy.
Merging Communities
You are viewing a single comment's thread. Return to all comments →
Optimized Union-Find Solution
The Union-Find data structure is a powerful tool for managing disjoint sets efficiently. Here's a concise approach:
Initialization:
parentandsizearrays where each node starts as its own parent and each set has size 1.Path Compression:
findfunction to flatten the tree structure and speed up future operations.Union by Size:
Query Operation:
findfunction.Python Code:
Usage Example:
For more insights and advanced techniques on Union-Find and related algorithms, visit EduHQ.
What happens if the input includes already connected nodes? Does this handle that efficiently?