Graph
Connected Components
547. Number of Provinces
Medium·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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