Skip to main content

Graph

Connected Components​

547. Number of Provinces​

Medium·
Explanation

Initialize a DSU with n nodes. Iterate the upper triangle of the matrix -- when isConnected[row][col] == 1, union the two cities. Each successful union reduces the component count by 1. Return getCount().

Analysis
Time
O(n^2 * α(n))
  • n is the number of cities.
  • Scanning the upper triangle of isConnected costs O(n^2) iterations.
  • Each union call does a find on both endpoints, which with path compression and union by rank is O(α(n)) amortized.
Space
O(3n)
  • parent, rank, and size are each their own length-n array inside DisjointSets - three separate O(n) allocations.
FIG. NUMBER OF PROVINCES● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
disjoint_set = DisjointSets(n)
 
for row in range(n):
for col in range(row + 1, n):
if isConnected[row][col]:
disjoint_set.union(row, col)
 
return disjoint_set.getCount()

323. Number of Connected Components in an Undirected Graph​

Medium·
Explanation

Initialize DSU with n nodes. Process every edge with union(a, b) -- each successful merge decreases the component count by 1. Return getCount() after all edges.

Analysis
Time
O(n + E * a(n))
  • DisjointSets(n) initializes parent, rank, and size, each of length n: O(n).
  • The for a, b in edges loop calls union once per edge; with union by rank and path compression, find runs in amortized O(a(n)) (inverse Ackermann, effectively constant), so all E union calls cost O(E * a(n)).
  • n is the number of nodes and E is the number of edges.
Space
O(n)
  • self.parent, self.rank, and self.size each hold n entries.
FIG. NUMBER OF CONNECTED COMPONENTS● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
disjoint_set = DisjointSets(n)
for a, b in edges:
disjoint_set.union(a, b)
return disjoint_set.getCount()

1971. Find if Path Exists in Graph​

Easy·
Explanation

Initialize DSU with n nodes. Union all edges. Two nodes are connected iff they share the same root -- return find(source) == find(destination).

Analysis
Time
O(E · α(n))
  • n = number of nodes, E = number of edges. The for a, b in edges loop calls union once per edge, each doing two find calls with path compression and union by rank - amortized O(α(n)) per call, giving O(E · α(n)) overall.
  • The final find(source) == find(destination) check is two more amortized O(α(n)) calls, dominated by the edge loop.
Space
O(n)
  • DisjointSets.__init__ allocates parent, rank, and size, each of length n.
FIG. FIND IF PATH EXISTS● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def validPath(
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
disjoint_sets = DisjointSets(n)
for a, b in edges:
disjoint_sets.union(a, b)
return disjoint_sets.find(source) == disjoint_sets.find(destination)

1101. The Earliest Moment When Everyone Become Friends​

Medium·
Explanation

Sort logs by timestamp. Initialize DSU with n nodes. Process each log entry -- union the two people. After each union, if getCount() == 1 all n people are in one component; return the current timestamp. If no such moment exists, return -1.

Analysis
Time
O(L * α(n) + L log L)
  • L is the number of log entries, n the number of people. Processing all logs costs L calls to union, each O(α(n)) amortized (path compression + union by rank) - L * α(n). Sorting the logs by timestamp first costs O(L log L), the dominant term.
Space
O(sort + n)
  • The DSU's parent, rank, and size arrays are each sized n, on top of the sort's own working memory.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. EARLIEST MOMENT FRIENDS● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
disjoint_set = DisjointSets(n)
logs.sort(key=lambda i: i[0])
 
for timestamp, a, b in logs:
disjoint_set.union(a, b)
if disjoint_set.getCount() == 1:
return timestamp
return -1

1319. Number of Operations to Make Network Connected​

Medium·
Explanation

If there are fewer than n-1 cables, it is impossible to connect all n computers regardless of how they are rearranged -- return -1. Otherwise, union every connection. Redundant edges (those that join two already-connected computers) are cables that can be unplugged and reused. After processing all connections, the DSU has some number of components k. Each component is already internally connected, so we need exactly k-1 cable moves to link them into one network.

Analysis
Time
O(E * α(n))
  • E is the number of connections. Each union call costs O(α(n)) amortized thanks to path compression and union by rank, and the loop makes one union call per connection.
Space
O(n)
  • The DSU's parent, rank, and size arrays are each sized n.
FIG. MAKE NETWORK CONNECTED● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
disjoint_sets = DisjointSets(n)
for a, b in connections:
disjoint_sets.union(a, b)
return disjoint_sets.getCount() - 1

Cycle Detection​

261. Graph Valid Tree​

Medium·
Explanation

A valid tree has exactly n-1 edges and no cycles. Initialize DSU with n nodes. For each edge (a, b), call union(a, b) -- if it returns False, the edge creates a cycle so the graph is not a tree. After all edges, check getCount() == 1 to ensure full connectivity.

Analysis
Time
O(E * a(n))
  • E is the number of edges, n is the number of nodes.
  • Each edge triggers one union call, which calls find (with path compression) on both endpoints and unions by rank - amortized O(a(n)) per call, where a is the inverse Ackermann function.
  • A cycle triggers an early return False, but the amortized bound already reflects the cheapest case for that call.
Space
O(n)
  • DisjointSets.__init__ allocates parent, rank, and size, each holding n entries.
FIG. GRAPH VALID TREE● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
disjoint_set = DisjointSets(n)
 
for a, b in edges:
if not disjoint_set.union(a, b):
return False
 
return disjoint_set.getCount() == 1

684. Redundant Connection​

Medium·
Explanation

Process each edge with union(a, b). When the two endpoints are already in the same component, the edge is redundant -- record it as result. Unlike Graph Valid Tree there is no early exit; we continue to find the last such edge. Return result after all edges.

Analysis
Time
O(E · α(n))
  • Each of the E edges triggers one union call costing O(α(n)) amortized (inverse Ackermann, from path compression + union by rank).
  • All E edges are always processed (no early exit), so the worst case is E · α(n).
Space
O(2n)
  • DisjointSets allocates a separate parent array and rank array, each of size n - 2n.
FIG. REDUNDANT CONNECTION● INTERACTIVE
visualization loads as you reach it
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
disjoint_sets = DisjointSets(1001)
result = None
for a, b in edges:
if not disjoint_sets.union(a, b):
result = [a, b]
return result

Component Size​

Journey to the Moon​

Medium·
Explanation

Group astronauts into nationality-based components with DSU. The answer is the total pairs C(n, 2) minus the sum of same-country pairs C(k, 2) for each component of size k.

Analysis
Time
O(E · α(n) + n)
  • E calls to union, each O(α(n)) amortized thanks to path compression (in find) and union by rank.
  • getSizes makes a single O(n) pass over the parent array to yield each component's root and size.
Space
O(n)
  • The DSU's parent, rank, and size arrays are each sized n.
FIG. JOURNEY TO THE MOON● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
def journeyToMoon(n, astronaut):
disjoint_sets = DisjointSets(n)
for a, b in astronaut:
disjoint_sets.union(a, b)
result = math.comb(n, 2)
for root, count in disjoint_sets.getSizes():
result -= math.comb(count, 2)
return result

Merging Communities ​

Hard·
Explanation

Initialize a DSU over n+1 elements (1-indexed). For each M query, union(i, j) attaches the smaller-rank tree under the larger, updating size[root]. For each Q query, getSize(i) calls find(i) with path compression to reach the root, then returns size[root] -- the community's current population.

Analysis
Time
O(Q * α(n))
  • Q is the number of queries, n the number of elements. Each M query runs union, and each Q query's getSize calls find internally - both are O(α(n)) amortized (path compression + union by rank), so Q queries total Q * α(n).
Space
O(n)
  • The DSU's parent, rank, and size arrays are each sized n.
FIG. MERGING COMMUNITIES● INTERACTIVE
visualization loads as you reach it
n, q = map(int, input().split())
disjoint_sets = DisjointSets(n + 1)
for _ in range(q):
op, i, *j = input().split()
if op == "M":
disjoint_sets.union(int(i), int(j[0]))
else:
print(disjoint_sets.getSize(int(i)))

Components in a graph​

Medium·
Explanation

Initialize a DSU of size 2 * len(gb) + 1 to cover all node labels. Union every edge. Iterate roots with getSizes() -- skip singletons (size < 2) and track the running minimum and maximum among the rest.

Analysis
Time
O(E · α(E))
  • E is the number of edges in gb. union is called once per edge, each costing O(α(E)) amortized thanks to union-by-rank and path compression.
  • getSizes() then does a single O(E) pass over the DSU's 2E + 1 slots to scan component sizes.
Space
O(E)
  • The DSU's parent, rank, and size arrays are each sized 2E + 1.
FIG. COMPONENTS IN GRAPH● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
def componentsInGraph(gb):
disjoint_sets = DisjointSets(2 * len(gb) + 1)
for a, b in gb:
disjoint_sets.union(a, b)
mini, maxi = float("inf"), -float("inf")
for root, size in disjoint_sets.getSizes():
if size >= 2:
mini = min(mini, size)
maxi = max(maxi, size)
return [mini, maxi]

Advanced Applications​

1202. Smallest String With Swaps​

Medium·
Explanation

Indices connected directly or transitively through pairs form a component -- characters within a component can be freely rearranged. Union all pairs to identify components, sort each component's characters, then place them back at the component's original indices in ascending order.

Analysis
Time
O((E + V) * α(V) + V log V)
  • Unioning all E pairs, each a find + union call, costs O(E * α(V)) amortized, where V = len(s) is the number of characters/indices.
  • Building components and the final reconstruction loop each call find once per index, O(V * α(V)) amortized.
  • sorted(components[comp], reverse=True) sorts every component's characters; summed across all components this is O(V log V) in the worst case (one component holding all V characters).
Space
O(sort + V)
  • parent, rank, and size in DisjointSets are each length V.
  • components holds every character exactly once across its lists, and result collects all V output characters.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. SMALLEST STRING SWAPS● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
disjoint_sets = DisjointSets(len(s))
for a, b in pairs:
disjoint_sets.union(a, b)
components = collections.defaultdict(list)
for idx, char in enumerate(s):
root = disjoint_sets.find(idx)
components[root].append(char)
for comp in components:
components[comp] = sorted(components[comp], reverse=True)
result = []
for idx in range(len(s)):
root = disjoint_sets.find(idx)
result.append(components[root].pop())
return "".join(result)

721. Accounts Merge​

Medium·
Explanation

Use account indices (0..n-1) as DSU elements. Build email_idx mapping each email to the index of the first account that introduced it. For each account, union email_idx[emails[0]] with email_idx[email] for every email -- when emails[0] was seen in an earlier account, this bridges the two account indices into one component. Then group emails by their root account index, sort each group, and prepend the account name.

Analysis
Time
O(N*K*a(N) + N*K*log(N*K))
  • N is the number of accounts, K is the max emails per account. The first loop unions and finds over up to N*K emails, costing O(N*K*a(N)) amortized, where a is the inverse Ackermann function.
  • The final loop sorts the emails within each component, costing O(N*K*log(N*K)) in the worst case.
Space
O(sort + N + N*K)
  • disjoint_sets's parent/rank/size arrays are size N.
  • email_idx and merged_accounts hold up to N*K entries total.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. ACCOUNTS MERGE● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
disjoint_sets = DisjointSets(len(accounts))
email_idx = {}
for idx, (name, *emails) in enumerate(accounts):
for email in emails:
if email not in email_idx:
email_idx[email] = idx
disjoint_sets.union(email_idx[emails[0]], email_idx[email])
 
merged_accounts = collections.defaultdict(list)
for email, idx in email_idx.items():
root = disjoint_sets.find(idx)
merged_accounts[root].append(email)
results = []
for root in merged_accounts:
results.append([accounts[root][0], *sorted(merged_accounts[root])])
return results

947. Most Stones Removed with Same Row or Column​

Medium·
Explanation

Map each stone to a connection between its row index and a shifted column index (col + 10001). Union the row and column nodes for every stone. Stones that share a row or column fall into the same DSU component. From a component of size k, exactly k - 1 stones can be removed (keep one). The answer is len(stones) - components, where components counts distinct roots among all nodes marked by a stone.

The key trick is using a single DSU of size 20002: rows occupy indices 0-9999 and columns occupy 10001-20001, so they never collide.

Analysis
Time
O(n · α(n))
  • The for row, col in stones loop performs one union per stone - n calls, each O(α(n)) amortized thanks to path compression and union by rank in DisjointSets - giving n · α(n).
  • The components = sum(...) pass iterates over the fixed-size DSU (range(20002)), a constant O(1) pass independent of n.
Space
O(1)
  • disjoint_sets and is_stone are always allocated at the fixed size 20002 (bounded by the coordinate range 0-10000, shifted), regardless of the number of stones n - constant space.
FIG. MOST STONES REMOVED● INTERACTIVE
visualization loads as you reach it
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
size = 20002
disjoint_sets = DisjointSets(size)
is_stone = [False] * size
for row, col in stones:
col += 10001
disjoint_sets.union(row, col)
is_stone[row] = is_stone[col] = True
components = sum(
is_stone[i] and disjoint_sets.find(i) == i for i in range(size)
)
return len(stones) - components

737. Sentence Similarity II​

Medium·
Explanation

Words in similarPairs that are directly or transitively connected form a component. Assign each unique word a stable DSU index using setdefault (first occurrence wins), then union every pair. For each position in zip(sentence1, sentence2), if the words differ, look both up in pair_idx -- if either is missing or they have different roots, return False. After the zip, check equal lengths.

Analysis
Time
O(P * α(P) + S * α(P))
  • P is the number of similarPairs, S is len(sentence1), α is the inverse Ackermann function.
  • The first loop builds pair_idx and calls disjoint_sets.union once per pair - O(P * α(P)) amortized.
  • The second loop walks S word pairs, each doing at most two disjoint_sets.find calls - O(S * α(P)) amortized.
Space
O(P)
  • disjoint_sets.parent, .rank, and .size are each sized 2 * len(similarPairs), so O(P).
  • pair_idx holds at most 2 * len(similarPairs) entries, also O(P).
FIG. SENTENCE SIMILARITY II● INTERACTIVE
visualization loads as you reach it
class DisjointSets:
def __init__(self, size):
self.parent = list(range(size)) # each element is its own root initially
self.rank = [0] * size # upper bound on tree height per root
self.size = [1] * size # component size (1 per node initially)
self.count = size # number of disjoint components
 
def find(self, element):
if self.parent[element] == element:
return element
# path compression: flatten the chain to the root on the way back
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
 
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
# union by rank: attach shorter tree under taller to keep height small
if self.rank[root_a] > self.rank[root_b]:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
elif self.rank[root_a] < self.rank[root_b]:
self.parent[root_a] = root_b
self.size[root_b] += self.size[root_a]
else:
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.rank[root_a] += 1 # only grows when both trees have equal rank
self.count -= 1
return True # merged: two components became one
return False # already connected: no merge happened
 
def getCount(self):
return self.count
 
def getSize(self, a):
return self.size[self.find(a)]
 
def getSizes(self):
for i in range(len(self.parent)):
if self.parent[i] == i:
yield self.parent[i], self.size[i]
 
 
class Solution:
def areSentencesSimilarTwo(
self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]
) -> bool:
disjoint_sets = DisjointSets(2 * len(similarPairs))
pair_idx = {}
for idx, (a, b) in enumerate(similarPairs):
pair_idx.setdefault(a, 2 * idx)
pair_idx.setdefault(b, 2 * idx + 1)
disjoint_sets.union(pair_idx[a], pair_idx[b])
for word1, word2 in zip(sentence1, sentence2):
if word1 != word2:
a = pair_idx.get(word1, None)
b = pair_idx.get(word2, None)
if a is None or b is None:
return False
if disjoint_sets.find(a) != disjoint_sets.find(b):
return False
return len(sentence1) == len(sentence2)

990. Satisfiability of Equality Equations​

Medium·
Explanation

First pass: iterate equations and union every == pair. DSU handles transitivity automatically -- if a==b and b==c, after both unions a and c share a root. Second pass: for each != pair, call find on both letters. If they share a root, some earlier == chain connected them, which directly contradicts the inequality -- return False. If every != pair has distinct roots, return True.

Analysis
Time
O(E)
  • DSU size is fixed at 26 (one node per lowercase letter), so every find/union call runs in O(alpha(26)), effectively O(1).
  • Two passes over the E equations, each doing O(1) DSU work per equation, give O(E) total.
Space
O(1)
  • The DSU's parent and rank arrays are fixed at size 26, regardless of E.
FIG. SATISFIABILITY EQUATIONS● INTERACTIVE
visualization loads as you reach it
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
disjoint_sets = DisjointSets(ord("z") + 1)
for a, eq, _, b in equations:
if eq == "=":
disjoint_sets.union(ord(a), ord(b))
for a, eq, _, b in equations:
if eq == "!" and disjoint_sets.find(ord(a)) == disjoint_sets.find(ord(b)):
return False
return True