Space
Open
From Fieldwork
Scales
Archive
The Setup (Constructor)
You need an array parent. Initially, everyone is their own parent.
Mnemonic: "I am my own boss."
The find function (Path Compression)
This is the most important part.
Logic: If I am not my own boss, go find my boss's boss, and save that result so I don't have to ask again next time.
Template: Recursive is easiest to remember.
Version A: The "Lazy" Union (No Rank)
Use this when you are short on time or the constraints are small (N<10,000). It just blindly sets one parent to the other.
Version B: The "Pro" Union (With Rank)
Use this for hard graph problems (N>100,000) or to impress an interviewer.
Logic: Find the roots. If they are different, check who is bigger (higher rank). The small one points to the big one. If they are equal, pick one to win and increase its rank.
https://aistudio.google.com/prompts/1Yj7xbJdZW_gmgxOCkb2ozD_4ER4HlWXX
class DSU:
def __init__(self, n):
self.parent = list(range(n))
# self.rank = [1] * n <-- Optional: Uncomment for efficiency
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
# Simple version (usually sufficient):
self.parent[root_i] = root_j
# Optimized version (replace line above with this):
# if self.rank[root_i] > self.rank[root_j]:
# self.parent[root_j] = root_i
# elif self.rank[root_j] > self.rank[root_i]:
# self.parent[root_i] = root_j
# else:
# self.parent[root_j] = root_i
# self.rank[root_i] += 1
return True
return FalsePractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode